Decomposing simple permutations, with enumerative consequences
An interval in the permutation \(\pi\) is a set of contiguous indices \(I=[a,b]\) such that the set of values \(\pi (I)=\{\pi (i):i\in I\}\) also forms an interval of natural numbers. Every permutation \(\pi\) of \([n]=\{1,2,\ldots ,n\}\) has intervals of size 0,1, and \(n\); \(\pi\) is said to be simple if it has no other intervals. The main result of this paper is the following: There is a function \(f(k)\) such that every simple permutation of length at least \(f(k)\) contains two simple subsequences, each of length at least \(k\), sharing at most two entries. Its proof gives a function \(f\) of order about \(k^{k}\). It is shown how this result has enumerative consequences. For example, it implies that, for any \(r\), the number of permutations with at most \(r\) copies of 132 has an algebraic generating function (this was previously proved, constructively, by \textit{M. Bóna} [Adv. Appl. Math. 18, No. 4, 510-522 (1997; Zbl 0879.05006)] and independently, by \textit{T. Mansour and A. Vainshtein} [Adv. Appl. Math. 28, No. 2, 185-195 (2002; Zbl 1005.05001)]. Applications to graph theory and convex geometry are also proposed.
- Counting occurrences of 132 in a permutation
- Counting occurrences of 132 in an even permutation
- Counting occurrences of 231 in an involution
- Counting occurrences of a pattern of type (1, 2) or (2, 1) in permutations
- Enumeration of permutations containing a prescribed number of occurrences of a pattern of length three
- Generalized permutation patterns and a classification of the Mahonian statistics
- Graph derivatives
- scientific article; zbMATH DE number 2186865 (Why is no real title available?)
- scientific article; zbMATH DE number 2127712 (Why is no real title available?)
- scientific article; zbMATH DE number 1478125 (Why is no real title available?)
- Indecomposable graphs
- On Intervals in Relational Structures
- Permutations with one or two 132-subsequences
- Restricted 132-alternating permutations and Chebyshev polynomials
- Restricted permutations
- Simple permutations and algebraic generating functions
- Simple permutations and pattern restricted permutations
- Simple permutations: Decidability and unavoidable substructures
- The enumeration of permutations with a prescribed number of ``forbidden patterns
- The number of permutations containing exactly one increasing subsequence of length three
- The number of permutations with exactly \(r\) 132-subsequences is \(P\)-recursive in the size!
- Almost avoiding permutations
- Characterising inflations of monotone grid classes of permutations
- Deciding whether there are infinitely many prime graphs with forbidden induced subgraphs
- A counterexample regarding labelled well-quasi-ordering
- Some relational structures with polynomial growth and their associated algebras. I: Quasi-polynomiality of the profile
- Scaling limits of permutation classes with a finite specification: a dichotomy
- An algorithm for deciding the finiteness of the number of simple permutations in permutation classes
- Permutations destroying arithmetic structure
- Simple permutations and algebraic generating functions
- Simple permutations: Decidability and unavoidable substructures
- The advantage of truncated permutations
- scientific article; zbMATH DE number 2186865 (Why is no real title available?)
- A survey of simple permutations
- Simple extensions of combinatorial structures
- Substitution-closed pattern classes
- Grid classes and partial well order
- Counting occurrences of patterns in permutations
- Small configurations in simple permutations
- Pin classes. II: Small pin classes
This page was built for publication: Decomposing simple permutations, with enumerative consequences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2377669)
