The enumeration of simple permutations
arXiv:math/0304213
Abstract
A simple permutation is one which maps no proper non-singleton interval onto an interval. We consider the enumeration of simple permutations from several aspects. Our results include a straightforward relationship between the ordinary generating function for simple permutations and that for all permutations, that the coefficients of this series are not P-recursive, an asymptotic expansion for these coefficients, and a number of congruence results.
22 pages, 1 figure, submitted to the Journal of Integer Sequences
Cited by in corpus (24)
- Universal limits of substitution-closed permutation classes
- Pattern avoidance is not P-recursive
- Grid polygons from permutations and their enumeration by the kernel method
- Equivalence Classes of Permutations under Various Relations Generated by Constrained Transpositions
- Decomposing simple permutations, with enumerative consequences
- Orders induced by segments in floorplan partitions and (2-14-3,3-41-2)-avoiding permutations
- Congruences for Catalan and Motzkin numbers and related sequences
- The Mobius Function of the Permutation Pattern Poset
- Decomposing Inversion Sets of Permutations and Applications to Faces of the Littlewood-Richardson Cone
- Deflatability of Permutation Classes
- Densities in large permutations and parameter testing
- Biased permutative equivariant categories
- Average-case analysis of perfect sorting by reversals (Journal Version)
- The Moebius function of separable and decomposable permutations
- On the X-rays of permutations
- Profile and hereditary classes of ordered relational structures
- Enumeration of permutations indexing local complete intersection Schubert varieties
- On the Möbius function of permutations under the pattern containment order
- Asymptotics of self-overlapping permutations
- Errata and Addenda to Mathematical Constants
- Intervals of permutations and the principal Möbius function
- A general method for common intervals
- An algorithm for deciding the finiteness of the number of simple permutations in permutation classes
- Longest Common Pattern between two Permutations