Nowa wersja platformy, zawierająca wyłącznie zasoby pełnotekstowe, jest już dostępna.
Przejdź na https://bibliotekanauki.pl

PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2018 | Vol. 163, nr 1 | 21--39
Tytuł artykułu

A Generating Tree for Permutations Avoiding the Pattern 122+3

Wybrane pełne teksty z tego czasopisma
Warianty tytułu
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.
Wydawca

Rocznik
Strony
21--39
Opis fizyczny
Bibliogr. 30 poz., rys., tab.
Twórcy
autor
autor
  • Dipartimento di Ingegneria dell’Informazione e Scienze Matematiche, Università di Siena, Siena, Italy, guerrini55@student.unisi.it
autor
  • Dipartimento di Ingegneria dell’Informazione e Scienze Matematiche, Università di Siena, Siena, Italy, rinaldi@unisi.it
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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.baztech-c153e866-d038-44bb-8872-3247aebee861
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.