Finitely labeled generating trees and restricted permutations
Journal of Symbolic Computation, 41 (2006), 559–572.
Generating trees are a useful technique in the enumeration of various combinatorial objects, particularly restricted permutations. Quite often, the generating tree for the set of permutations avoiding a set of restrictions Q requires infinitely many labels. However, sometimes this generating tree only needs finitely many labels. We characterize the finite sets of restrictions Q for which this phenomenon occurs. We also present an algorithm — in fact, a special case of an algorithm of Zeilberger — that is guaranteed to find such a generating tree if it exists.
Download the paper:
- download from the journal website (subscription required)
- ps
- source: tex and bib
Related links:
- The accompanying Maple package, FINLABEL.
- An extended abstract about this work (written for the 2nd Annual International Conference on Permutation Patterns) is available in pdf, ps, or source.
- My paper "Enumeration schemes for restricted permutations" considers another systematic approach to the enumeration of restricted permutations, which is implemented in the Maple package WILFPLUS.