Simple permutations and algebraic generating functions
With Robert Brignall and Sophie Huczynska.
Journal of Combinatorial Theory, Series A 115 (2008), 423–441.
A simple permutation is one that never maps a nontrivial contiguous set of indices contiguously. Given a set of permutations that is closed under taking subpermutations and contains only finitely many simple permutations, we provide a framework for enumerating subsets that are restricted by properties belonging to a finite “query-complete set”. Such properties include being even, being an alternating permutation, and avoiding a given generalised (blocked or barred) pattern. We show that the generating functions for these subsets are always algebraic, thereby generalising recent results of Albert and Atkinson. We also apply these techniques to the enumeration of involutions and cyclic closures.
Download the paper:
Related links:
- Slides (pdf) for a talk Robert gave about this work at the Fourth International Conference on Permutations Patterns.
- Example 4.1 (the class of separable permutations) is counted by sequence A006318 in the OEIS.
- Example 4.2 (the wreath closure of 1, 12, 21, and 2413) is counted by sequence A120346 in the OEIS.
- Example 4.4 (permutations avoiding 2413, 3142, and 2143) is counted by sequence A033321 in the OEIS.
- Example 4.5 (the set of alternating separable permutations) is counted by sequence A121703 in the OEIS.
- Example 5.4 (the set of separable involutions) is counted by sequence A121704 in the OEIS.
- Example 6.3 (the cyclic closure of Av(132)) is counted by sequence A141253 in the OEIS.
- The even separable permutations are counted by sequence A165328 in the OEIS.
- A non-example: separable derangements.