Finitely labeled generating trees and restricted permutations

2003/09/15 by Vince Vatter, Vatter, Vince
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO

paper · pdf · doi:10.48550/arxiv.math/0309238

Accepted by J. Symb. Comp.; 12 pages

arxiv created 2005/10/06 · arxiv updated 2009/12/01

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.

Related

• Subregularity in infinitely labeled generating trees of restricted permutations
• A generating tree with a single label for permutations avoiding the vincular pattern 1-32-4
• Generating trees for permutations avoiding generalized patterns
• Combinatorial generation via permutation languages. VI. Binary trees
• An algorithm computing combinatorial specifications of permutation\n classes