A Generating Tree for Permutations Avoiding the Pattern 122+3

• Autorzy: Duchi, E. , Guerrini, V. , Rinaldi, S.
• Języki publikacji: EN

Abstrakty

EN

In this paper we study the family of permutations avoiding the pattern 122⁺3 (trivially equivalent to those avoiding 1 23 4), which extend the popular 123-avoiding permutations. In particular we provide an algorithmic description of a generating tree for these permutations, that is a way to build every object of a given size n + 1 in a unique way by performing local modifications on an object of size n. Our algorithm leads to a direct bijection between 1 23 4-avoiding permutations and valley-marked Dyck paths. It extends a known bijection between 123-avoiding permutations and Dyck paths, and makes explicit the connection between these objects that was earlier obtained by Callan through a series of non-trivial bijective steps. In particular our construction is simple enough to allow for efficient exhaustive generation.

Słowa kluczowe

EN

pattern avoiding permutations; generating trees; 1-23-4 avoiding permutations; valley marked Dyck paths

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2018
• Tom: Vol. 163, nr 1
• Strony: 21--39
• Opis fizyczny: Bibliogr. 30 poz., rys., tab.

Twórcy

autor

Duchi, E.

• Institut de Recherche en Informatique Fondamentale (IRIF), Université Paris Diderot, Paris, France,

autor

Guerrini, V.

• Dipartimento di Ingegneria dell’Informazione e Scienze Matematiche, Università di Siena, Siena, Italy,

autor

Rinaldi, S.

• Dipartimento di Ingegneria dell’Informazione e Scienze Matematiche, Università di Siena, Siena, Italy,

Bibliografia

• [1] Babson E, Steingrìmsson E. Generalized permutation patterns and a classification of the Mahonian statistics, Sem. Lothar. Combin. 2000;44(B44b):547-548.
• [2] Bacchelli S, Barcucci E, Grazzini E, Pergola E. Exhaustive generation of combinatorial objects by ECO, Acta Informatica 2004;40:585-602. doi:10.1007/s00236-004-0139-x.
• [3] Bafna V, Pevzner PA. Genome rearrangements and sorting by reversals, 34th Annual Symposium on Foundations of Computer Science (Palo Alto, CA, 1993), IEEE Comput. Soc. Press, Los Alamitos, CA, 1993 pp. 148-157. doi:10.1109/SFCS.1993.366872.
• [4] Banderier C, Bousquet-Mélou M, Denise A, Flajolet P, Gardy D, Gouyou-Beauchamps D. Generating functions for generating trees, Disc. Math. 2002;246(1-3):29-55. URL https://hal.archives-ouvertes.fr/hal-00003258.
• [5] Barcucci E, Del Lungo A, Pergola E, Pinzani R. ECO: a methodology for the Enumeration of Combinatorial Objects, J. Diff. Eq. and App. 1999;5:435-490. URL https://doi.org/10.1080/10236199908808200.
• [6] Björner A. The Möbius function of subword order, Invariant theory and tableaux (Minneapolis, MN, 1988), 118-124, IMA, Math. Appl., vol. 19, Springer, New York, (1990). URL http://adsabs.harvard.edu/abs/1990IMA....19..118B.
• [7] Bona M. Combinatorics of Permutations, Second Edition (2012), Chapman and Hall/CRC. ISBN:9781439850510.
• [8] Bousquet-Mélou M. Four classes of pattern-avoiding permutations under one roof: generating trees with two labels, Electronic J. Combinatorics 2003;9(2):49-67. URL https://hal.archives-ouvertes.fr/hal-00307835.
• [9] Burstein A. Enumeration of Words with Forbidden Patterns, Ph.D. Thesis, University of Pennsylvania, (1998).
• [10] Callan D. A bijection to count (1 — 23 — 4)-avoiding permutations, arxiv:1008.2375.v1.
• [11] Claesson A. Generalized Pattern Avoidance, European J. Combinatorics 2001;22(7):961-971. URL https://doi.org/10.1006/eujc.2001.0515.
• [12] Dairyko M, Pudwell L, Tyner S, Wynn C. Non-contiguous pattern avoidance in binary trees, Electr. J. Combin., 2012;19(3): P22.
• [13] Dulio P, Pagani SMC, Frosini A. A geometrical characterization of regions of uniqueness and applications to discrete tomography, Inverse Problems, 2015;31(12):125011, doi:10.1088/0266-5611/31/12/125011.
• [14] Dulio P, Pagani SMC, Frosini A. Regions of uniqueness quickly reconstructed by three directions in discrete tomography, Fundamenta Informaticae, 2017;155(4):407-423. doi:10.3233/FI-2017-1592.
• [15] Elizalde S. Asymptotic enumeration of permutations avoiding generalized patterns, Advances in Applied Mathematics 2006;36(2):138-155. URL https://doi.org/10.1016/j.aam.2005.05.006.
• [16] Frosini A, Guerrini V, Rinaldi S. Geometric properties of matrices induced by pattern avoidance, Theoretical Computer Science 2016;624:109-120. URL https://doi.org/10.1016/j.tcs.2015.11.012.
• [17] Frosini A, Picoleau C. How to decompose a binary matrix into three hv-convex polyominoes, R. Gonzales-Diaz et al. (Eds.): DGCI 2013, LNCS vol. 7749 Springer, Heidelberg 2013 pp. 311-323. doi:10.1007/978-3-642-37067-0_27.
• [18] Goyt A. Avoidance of partitions of a three element set, Adv. Appl. Math., 2008;41(1):95-114. URL https://doi.org/10.1016/j.aam.2006.07.006.
• [19] Klazar M. On abab-free and abba-free sets partitions, European J. Combin., 1996;17(1):53-68. URL https://doi.org/10.1006/eujc.1996.0005.
• [20] Krattenthaler C. Permutations with Restricted Patterns and Dyck Paths, Advances in Applied Mathematics 2000;27(2-3):510-530. doi:10.1006/aama.2001.0747.
• [21] Knuth DE. The Art of Computer Programming Vol. 1, (1968) Boston: Addison-Wesley.
• [22] OEIS Foundation Inc., The On-line Encyclopedia of Integer Sequences, http://oeis.org (2011).
• [23] Pratt VR. Computing permutations with double-ended queues. Parallel stacks and parallel queues, Proc. Fifth Annual ACM Symposium on Theory of Computing (Austin, Tex., 1973), 1973 pp. 268-277. doi:10.1145/800125.804058.
• [24] Rosenstiehl P, Tarjan R. Gauss codes, planar Hamiltonian graphs, and stack-sortable permutations, Journal of Algorithms, 1984;5(3):375-390. URL https://doi.org/10.1016/0196-6774(84)90018-X.
• [25] Rowland E. Pattern avoidance in binary trees, J. Combin. Theory Ser. A, 2010;117:741-758. doi:10.1016/j.jcta.2010.03.004.
• [26] Sagan BE. Pattern avoidance in set partitions, Ars Combin., 2010;94:79-96.
• [27] Simion R, Schmidt F. Restricted permutations, European Journal of Combinatorics, 1985;6(4):383-406. URL https://doi.org/10.1016/S0195-6698(85)80052-4.
• [28] Stanley RP. Enumerative Combinatorics, Vol. 2, Cambridge University Press, Cambridge (1999). ISBN-13:978-0521560696, 10:0521560691.
• [29] Tarjan R. Sorting using networks of queues and stacks, Journal of the ACM 1972;19(2):341-346. doi:10.1145/321694.321704.
• [30] Watterson GA, Ewens WJ, Hall T, Morgan A. The chromosome inversion problem, J. Theor. Biol. 1982;99(1):1-7. URL https://doi.org/10.1016/0022-5193(82)90384-8.

Identyfikatory

DOI

10.3233/FI-2018-1730