Enumeration schemes for restricted permutations
Combinatorics, Probability and Computing, 17 (2008), 137–159.
Doron Zeilberger's enumeration schemes can be used to completely automate the enumeration of many permutation classes. We extend his enumeration schemes so that they apply to many more permutation classes and describe the Maple package WILFPLUS, which implements this process. We also compare enumeration schemes to three other systematic enumeration techniques: generating trees, substitution decompositions, and the insertion encoding.
Download the paper:
- from the journal
- ps
- source: tex and bbl
Related links:
- The accompanying Maple package, WILFPLUS
- Zeilberger's original enumeration schemes are described in his paper “Enumeration schemes, and more importantly, their automatic generation.”
- Question 9.4 (is it decidable if a permutation class contains only finitely many simple permutations?) has since been answered. See “Simple permutations: decidability and unavoidable substructions” by Brignall, Ruškuc, and Vatter.