Decomposing simple permutations, with enumerative consequences

Abstract

We prove that every sufficiently long simple permutation contains two long almost disjoint simple subsequences. This result has applications to the enumeration of restricted permutations. For example, it immediately implies a result of Bona and (independently) Mansour and Vainshtein that for any r, the number of permutations with at most r copies of 132 has an algebraic generating function.

References in corpus (3)

• The enumeration of simple permutations
• Simple permutations: decidability and unavoidable substructures
• Simple permutations and algebraic generating functions

Cited by in corpus (4)

• Simple permutations: decidability and unavoidable substructures
• Simple permutations and algebraic generating functions
• Longest Common Separable Pattern between Permutations
• Wreath Products of Permutation Classes