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
Some general results in combinatorial enumeration
Published online by Cambridge University Press: 05 October 2010
- 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
This survey article is devoted to general results in combinatorial enumeration. The first part surveys results on growth of hereditary properties of combinatorial structures. These include permutations, ordered and unordered graphs and hypergraphs, relational structures, and others. The second part advertises four topics in general enumeration: 1. counting lattice points in lattice polytopes, 2. growth of context-free languages, 3. holonomicity (i.e., P-recursiveness) of numbers of labeled regular graphs and 4. ultimate modular periodicity of numbers of MSOL-definable structures.
Introduction
We survey some general results in combinatorial enumeration. A problem in enumeration is (associated with) an infinite sequence P = (S1, S2, …) of finite sets Si. Its counting function fP is given by fP (n) = |Sn|, the cardinality of the set Sn. We are interested in results of the following kind on general classes of problems and their counting functions.
Scheme of general results in combinatorial enumeration. The counting function fP of every problem P in the class C belongs to the class of functions F. Formally, {fP | P ∈ C} ⊂ F.
The larger C is, and the more specific the functions in F are, the stronger the result. The present overview is a collection of many examples of this scheme.
- Type
- Chapter
- Information
- Permutation Patterns , pp. 3 - 40Publisher: Cambridge University PressPrint publication year: 2010
References
- 5
- Cited by