Finitely labeled generating trees and restricted permutations

DOI10.1016/J.JSC.2005.10.003MaRDI QIDQ2457348zbMATH OpenOpenAlexFDO

Authors Vincent Vatter

Publication date 23 October 2007

Published in Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0309238

zbMATH Keywords

forbidden subsequencegenerating treeRestricted permutation

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Nonnumerical algorithms (68W05)

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.

Recommendations

• Subregularity in infinitely labeled generating trees of restricted permutations
• Permutation labeling for some trees
• A REFINED ENUMERATION OF p-ARY LABELED TREES
• On the exponential generating function of labelled trees
• A generalized enumeration of labeled trees and reverse Prüfer algorithm
• Restricted generating trees for weak orderings
• A generating tree approach to k-nonnesting partitions and permutations
• Generating functions for multi-labeled trees
• Generating trees for partitions and permutations with no k-nestings
• Enumeration of labelled \((k,m)\)-trees

Cites work

• A combinatorial proof of J. West's conjecture
• An algebraic characterization of the set of succession rules
• Classification of forbidden subsequences of length 4
• Counting 1324-avoiding permutations
• ECO method and hill-free generalized Motzkin paths
• ECO:a methodology for the enumeration of combinatorial objects
• Enumeration of vexillary involutions which are equal to their mirror/complement
• Enumeration schemes and, more importantly, their automatic generation
• Explicit enumeration of 321, hexagon-avoiding permutations
• Finite transition matrices for permutations avoiding pairs of length four patterns
• Forbidden subsequences
• Forbidden subsequences and Chebyshev polynomials
• Four classes of pattern-avoiding permutations under one roof: Generating trees with two labels
• From Motzkin to Catalan permutations
• From object grammars to ECO systems
• Generating functions for generating trees
• Generating trees and forbidden subsequences
• Generating trees and the Catalan and Schröder numbers
• scientific article; zbMATH DE number 2127714 (Why is no real title available?)
• scientific article; zbMATH DE number 1196088 (Why is no real title available?)
• scientific article; zbMATH DE number 1033382 (Why is no real title available?)
• scientific article; zbMATH DE number 1552331 (Why is no real title available?)
• scientific article; zbMATH DE number 2107707 (Why is no real title available?)
• scientific article; zbMATH DE number 1447312 (Why is no real title available?)
• scientific article; zbMATH DE number 3019031 (Why is no real title available?)
• Matchings avoiding partial patterns
• Partially well-ordered closed sets of permutations
• Permutations avoiding two patterns of length three
• Permutations with forbidden subsequences and a generalized Schröder number
• Permutations with forbidden subsequences and nonseparable planar maps
• Restricted permutations
• Symmetric functions and P-recursiveness
• The insertion encoding of permutations
• The number of Baxter permutations
• The tennis ball problem

Cited in

(20)

• Generating permutations with restricted containers
• Generating functions for multi-labeled trees
• Subregularity in infinitely labeled generating trees of restricted permutations
• Ascent sequences avoiding pairs of patterns
• Permutation patterns and cell decompositions
• Labelled trees and factorizations of a cycle into transpositions
• Generating trees for permutations avoiding generalized patterns
• Locally convex words and permutations
• Applications of the finite state automata in the enumerative combinatorics
• Stack-sorting for words
• The weak order on pattern-avoiding permutations
• scientific article; zbMATH DE number 1552331 (Why is no real title available?)
• Automatic discovery of structural rules of permutation classes
• Enumeration and Wilf-classification of permutations avoiding four patterns of length 4
• Enumeration Schemes for Restricted Permutations
• Restricted generating trees for weak orderings
• Asymptotic normality of consecutive patterns in permutations encoded by generating trees with one‐dimensional labels
• Combinatorial exploration: an algorithmic framework for enumeration
• The enumeration of inversion sequences avoiding the patterns 201 and 210
• Finding regular insertion encodings for permutation classes

Describes a project that uses

Uses Software

• InsEnc
• WILF
• HERB

This page was built for publication: Finitely labeled generating trees and restricted permutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2457348)