Affordable Access

Finitely labeled generating trees and restricted permutations

Authors
Type
Preprint
Publication Date
Submission Date
Identifiers
arXiv ID: math/0309238
Source
arXiv
License
Unknown
External links

Abstract

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 patterns requires infinitely many labels. Sometimes, however, this generating tree needs only finitely many labels. We characterize the finite sets of patterns 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.

Statistics

Seen <100 times