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:
- My paper “Finding regular insertion encodings for permutation classes” describes a systematic method of computing the “insertion encoding” for some permutation classes. This insertion encoding method can handle all of the classes which can be handled with finitely labeled generating trees, in addition to others.
- 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.