Decomposing simple permutations, with enumerative consequences
With Robert Brignall and Sophie Huczynska.
Combinatorica, 28 (2008), 385–400.
We prove that all sufficiently long simple permutations contain either long parallel alternations, long wedge simple permutations, or long proper pin sequences. From this it follows that every sufficiently long simple permutation contains two long almost disjoint simple subpermutations, which in turn immediately implies a result of Bóna 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.
Download the paper:
- download from the journal (subscription required)
- ps
- source: tex and bbl
Related links:
- Slides (pdf) for a talk Robert gave about this work at the Fourth International Conference on Permutations Patterns.