Decomposing simple permutations, with enumerative consequences

2006/06/08 by Brignall, Robert, Huczynska, Sophie, Vatter, Vince
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.math/0606186

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.

Related

• The enumeration of simple permutations
• Simple permutations and algebraic generating functions
• A Combinatorial Proof for 132-Avoiding Permutations with a Unique Longest Increasing Subsequence
• Simple permutations: decidability and unavoidable substructures
• A Survey of Simple Permutations