Book contents
- Frontmatter
- Contents
- Preface
- Some general results in combinatorial enumeration
- A survey of simple permutations
- Permuting machines and permutation patterns
- On three different notions of monotone subsequences
- A survey on partially ordered patterns
- Generalized permutation patterns – a short survey
- An introduction to structural methods in permutation patterns
- Combinatorial properties of permutation tableaux
- Enumeration schemes for words avoiding permutations
- The lexicographic first occurrence of a I-II-III-pattern
- Enumeration of partitions by rises, levels and descents
- Restricted patience sorting and barred pattern avoidance
- Permutations with k-regular descent patterns
- Packing rates of measures and a conjecture for the packing density of 2413
- On the permutational power of token passing networks
- Problems and conjectures
- References
An introduction to structural methods in permutation patterns
Published online by Cambridge University Press: 05 October 2010
Book contents
- Frontmatter
- Contents
- Preface
- Some general results in combinatorial enumeration
- A survey of simple permutations
- Permuting machines and permutation patterns
- On three different notions of monotone subsequences
- A survey on partially ordered patterns
- Generalized permutation patterns – a short survey
- An introduction to structural methods in permutation patterns
- Combinatorial properties of permutation tableaux
- Enumeration schemes for words avoiding permutations
- The lexicographic first occurrence of a I-II-III-pattern
- Enumeration of partitions by rises, levels and descents
- Restricted patience sorting and barred pattern avoidance
- Permutations with k-regular descent patterns
- Packing rates of measures and a conjecture for the packing density of 2413
- On the permutational power of token passing networks
- Problems and conjectures
- References
Summary
Abstract
Structural methods as applied to the study of classical permutation pattern avoidance are introduced and described. These methods allow for more detailed study of pattern classes, answering questions beyond basic enumeration. Additionally, they frequently can be applied wholesale, producing results valid for a wide collection of pattern classes, rather than simply ad hoc application to individual classes.
Introduction
In the study of permutation patterns, the important aspects of permutations of [n] = {1, 2, …, n} are considered to be the relative order of both the argument and the value. Specifically, we study a partial order, denoted ≼ and called involvement, on the set of such permutations where π ∈ Sk is involved in σ ∈ Sn, i.e. π ≼ σ if, for some increasing function f : [k] → [n] and all 1 ≤ i < j ≤ k, σ(i) < σ(j) if and only if π(f(i)) < π(f(j)). This dry and uninformative definition is necessary to get us started, but the reader should certainly be aware that another definition of involvement is that some of the points in the graph of π can be erased so that what remains is the graph of σ (possibly with a non-uniform scale on both axes) – in other words the pattern of σ (its graph) occurs as part of the pattern of π.
- Type
- Chapter
- Information
- Permutation Patterns , pp. 153 - 170Publisher: Cambridge University PressPrint publication year: 2010
References
[1] . Aspects of separability. Abstract for Permutation Patterns 2007.
[2] and . Simple permutations and pattern restricted permutations. Discrete Math., 300(1-3):1–15, 2005.Google Scholar
[3] , , and . The enumeration of simple permutations. J. Integer Seq., 6(4):Article 03.4.4, 18 pp., 2003.Google Scholar
[4] , , and . Regular closed sets of permutations. Theoret. Comput. Sci., 306(1-3):85–100, 2003.Google Scholar
[5] , , , , and . On the Wilf-Stanley limit of 4231-avoiding permutations and a conjecture of Arratia. Adv. in Appl. Math., 36(2):95–105, 2006.Google Scholar
[7] , , and . The insertion encoding of permutations. Electron. J. Combin., 12(1):Research paper 47, 31 pp., 2005.Google Scholar
[8] . On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern. Electron. J. Combin., 6:Note, N1, 4 pp., 1999.Google Scholar
[9] , , and . Permutations generated by token passing in graphs. Theoret. Comput. Sci., 178(1-2):103–118, 1997.Google Scholar
[10] , , and . Partially well-ordered closed sets of permutations. Order, 19(2):101–113, 2002.Google Scholar
[11] and . Restricted permutations and the wreath product. Discrete Math., 259(1-3):19–36, 2002.Google Scholar
[12] , , , and . Exhaustive generation of combinatorial objects by ECO. Acta Inform., 40(8):585–602, 2004.Google Scholar
[13] , , , , , and . Generating functions for generating trees. Discrete Math., 246(1-3):29–55, 2002.Google Scholar
[14] , , , and . From Motzkin to Catalan permutations. Discrete Math., 217(1-3):33–49, 2000.Google Scholar
[15] , , , and . Permutations avoiding an increasing number of length-increasing forbidden subsequences. Discrete Math. Theor. Comput. Sci., 4(1):31–44, 2000.Google Scholar
[16] . Four classes of pattern-avoiding permutations under one roof: generating trees with two labels. Electron. J. Combin., 9(2):Research paper 19, 31 pp., 2003.Google Scholar
[17] . Wreath products of permutation classes. Electron. J. Combin., 14(1):Research paper 46, 15 pp., 2007.Google Scholar
[18] , , and . Decomposing simple permutations, with enumerative consequences. Combinatorica, 28:385–400, 2008.Google Scholar
[19] , , and . Simple permutations and algebraic generating functions. J. Combin. Theory Ser. A, 115(3):423–441, 2008.Google Scholar
[20] , , and . Simple permutations: decidability and unavoidable substructures. Theoret. Comput. Sci., 391(1–2):150–163, 2008.Google Scholar
[21] and . The algebraic theory of context-free languages. In Computer programming and formal systems, pages 118–161. North-Holland, Amsterdam, 1963.Google Scholar
[22] and . Forbidden subsequences and Chebyshev polynomials. Discrete Math., 204(1-3):119–128, 1999.Google Scholar
[23] , , and . From object grammars to ECO systems. Theoret. Comput. Sci., 314(1-2):57–95, 2004.Google Scholar
[27] , , and . Vexillary involutions are enumerated by Motzkin numbers. Ann. Comb., 5(2):153–147, 2001.Google Scholar
[28] and . Introduction to automata theory, languages, and computation. Addison-Wesley Publishing Co., Reading, Mass., 1979. Addison-Wesley Series in Computer Science.Google Scholar
[29] and . Grid classes and the Fibonacci dichotomy for restricted permutations. Electron. J. Combin., 13:Research paper 54, 14 pp., 2006.Google Scholar
[30] and . On growth rates of closed permutation classes. Electron. J. Combin., 9(2):Research paper 10, 20 pp., 2003.Google Scholar
[31] . The art of computer programming. Vol. 1: Fundamental algorithms. Addison-Wesley Publishing Co., Reading, Mass., 1969.Google Scholar
[32] and . Finite transition matrices for permutations avoiding pairs of length four patterns. Discrete Math., 268(1-3):171–183, 2003.Google Scholar
[33] . Completion of the Wilf-classification of 3-5 pairs using generating trees. Electron. J. Combin., 13(1):Research paper 31, 19 pp., 2006.Google Scholar
[34] and . Restricted 132-avoiding permutations. Adv. in Appl. Math., 26(3):258–269, 2001.Google Scholar
[35] and . Excluded permutation matrices and the Stanley-Wilf conjecture. J. Combin. Theory Ser. A, 107(1):153–160, 2004.Google Scholar
[36] . Permutation classes of every growth rate above 2.48188. Mathematika, 56:182–192, 2010.Google Scholar
[37] . Small permutation classes. arXiv:0712.4006v2 [math.CO].
[38] . Finitely labeled generating trees and restricted permutations. J. Symbolic Comput., 41(5):559–572, 2006.Google Scholar
[39] . Generating trees and the Catalan and Schröder numbers. Discrete Math., 146(1-3):247–262, 1995.Google Scholar
[40] . Generating trees and forbidden subsequences. Discrete Math., 157(1-3):363–374, 1996.Google Scholar