Finitely labeled generating trees and restricted permutations

Generating trees represent 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.

• Publication year

  2003

• Venue

  Journal of symbolic computation

• Publication date

  2003-09-15

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/j.jsc.2005.10.003arXiv math/0309238
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Combinatorics of permutations

  2022cited by this paper
• The Insertion Encoding of Permutations

  2005cited by this paper
• Matchings Avoiding Partial Patterns

  2005cited by this paper
• From object grammars to ECO systems

  2004cited by this paper
• Enumerative Results on Integer Partitions Using the ECO Method

  2004cited by this paper
• Counting 1324-Avoiding Permutations

  2003cited by this paper
• Four Classes of Pattern-Avoiding Permutations Under One Roof: Generating Trees with Two Labels

  2003cited by this paper
• Finite transition matrices for permutations avoiding pairs of length four patterns

  2003cited by this paper
• Permutations Avoiding Two Patterns of Length Three

  2003cited by this paper
• Restricted permutations, antichains, atomic classes and stack sorting

  2003cited by this paper
• Generating functions for generating trees

  2002cited by this paper
• Sorting with a Forklift

  2002cited by this paper
• Partially Well-Ordered Closed Sets of Permutations

  2002cited by this paper
• A Prolific Construction of Strongly Regular Graphs with the n-e.c. Property

  2002cited by this paper
• An algebraic characterization of the set of succession rules

  2002cited by this paper
• The Tennis Ball Problem

  2002cited by this paper
• ECO method and hill-free generalized Motzkin paths

  2001cited by this paper
• Explicit enumeration of 321, hexagon-avoiding permutations

  2001cited by this paper
• An Algebra for Proper Generating Trees

  2000cited by this paper
• From Motzkin to Catalan permutations

  2000cited by this paper
• Permutations avoiding an increasing number of length-increasing forbidden subsequences

  2000cited by this paper
• Enumeration of vexillary involutions which are equal to their mirror/complement

  2000cited by this paper
• Permutations with forbidden subsequences and a generalized Schro"der number

  2000influential reference
• Restricted permutations

  1999cited by this paper
• Forbidden subsequences and Chebyshev polynomials

  1999cited by this paper
• ECO:a methodology for the enumeration of combinatorial objects

  1999cited by this paper
• Enumeration Schemes and, more importantly, their automatic generation

  1998influential reference
• A combinatorial proof of J. West's conjecture

  1998cited by this paper
• Schrder Triangles, Paths, and Parallelogram Polyominoes

  1998cited by this paper
• Permutations with forbidden subsequences and nonseparable planar maps

  1996cited by this paper
• Generating trees and forbidden subsequences

  1996influential reference
• Classification of Forbidden Subsequences of Length 4

  1996cited by this paper
• Generating trees and the Catalan and Schröder numbers

  1995cited by this paper
• Forbidden subsequences

  1994cited by this paper
• Symmetric functions and P-recursiveness

  1990cited by this paper
• Enumerative Combinatorics

  1986cited by this paper
• The Number of Baxter Permutations

  1977cited by this paper

• The enumeration of inversion sequences avoiding the patterns 201 and 210

  2023cites this paper
• Combinatorial Exploration: An Algorithmic Framework for Enumeration

  2022cites this paper
• Uncountably many enumerations of well-quasi-ordered permutation classes

  2022cites this paper
• Statistics on Almost-Fibonacci Pattern-Avoiding Permutations

  2022cites this paper
• Subregularity in infinitely labeled generating trees of restricted permutations

  2021influential citation
• Enumeration and Wilf-classification of permutations avoiding five patterns of length 4

  2020cites this paper
• Asymptotic normality of consecutive patterns in permutations encoded by generating trees with one‐dimensional labels

  2020cites this paper
• Stack-sorting for words

  2018cites this paper
• Permutation Patterns and Cell Decompositions

  2018cites this paper
• Permutation Patterns and Cell Decompositions

  2018cites this paper
• Automatic discovery of structural rules of permutation classes

  2017cites this paper
• Wilf classification of triples of 4-letter patterns II

  2017cites this paper
• Pattern Avoidance in Reverse Double Lists

  2017cites this paper
• Generating permutations with restricted containers

  2015influential citation
• The Weak Order on Pattern-avoiding Permutations

  2014cites this paper
• Ascent Sequences Avoiding Pairs of Patterns

  2014influential citation
• Combinatorial Gray Code for generating tree of permutation with two cycles

  2014cites this paper
• Locally Convex Words and Permutations

  2014cites this paper
• Inflations of geometric grid classes: three case studies

  2012cites this paper
• Algorithms for permutation statistics

  2011cites this paper
• Finding regular insertion encodings for permutation classes

  2009cites this paper
• ENUMERATION SCHEMES FOR PATTERN-AVOIDING WORDS AND PERMUTATIONS

  2008influential citation
• Online methods for network endpoint localization

  2007cites this paper
• Small permutation classes

  2007cites this paper
• On Growth Rates of Permutations, Set Partitions, Ordered Graphs and Other Objects

  2007cites this paper
• Device for coding and decoding

  2007cites this paper
• Vincent Vatter — Project Description

  2006cites this paper
• Inference methods for message endpoint localization in networks.

  2006cites this paper
• Completion of the Wilf-Classification of 3-5 Pairs Using Generating Trees

  2006influential citation
• The Insertion Encoding of Permutations

  2005cites this paper
• Enumeration Schemes for Restricted Permutations

  2005cites this paper
• Enumerative and structural applications of profile classes

  2004cites this paper
• Wilf classification of triples of 4-letter patterns I

  year unknowncites this paper