Enumeration Schemes for Restricted Permutations

Zeilberger's enumeration schemes can be used to completely automate the enumeration of many permutation classes. We extend his enumeration schemes so that they apply to many more permutation classes and describe the Maple package WilfPlus, which implements this process. We also compare enumeration schemes to three other systematic enumeration techniques: generating trees, substitution decompositions, and the insertion encoding.

• Publication year

  2005

• Venue

  Combinatorics, probability & computing

• Publication date

  2005-10-03

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1017/S0963548307008516arXiv math/0510044
• 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
• A combinatorial problem in geometry

  2009cited by this paper
• Simple permutations: Decidability and unavoidable substructures

  2006cited by this paper
• On the equivalence problem for succession rules

  2005cited by this paper
• Problems and conjectures presented at the Third International Conference on Permutation Patterns (University of Florida, March 7-11, 2005)

  2005cited by this paper
• On the Stanley--Wilf limit of 4231-avoiding permutations and a conjecture of Arratia

  2005cited by this paper
• On the equivalence problem for succession rules

  2005influential reference
• Reduced decompositions and permutation patterns

  2005cited by this paper
• The Insertion Encoding of Permutations

  2005cited by this paper
• Simple permutations and pattern restricted permutations

  2005cited by this paper
• Wilf Classes of Pairs of Permutations of Length 4

  2005cited by this paper
• Pattern Avoidance Classes and Subpermutations

  2004cited by this paper
• On an open problem of Green and Losonczy: exact enumeration of freely braided permutations

  2004cited by this paper
• On the least exponential growth admitting uncountably many closed permutation classes

  2003cited by this paper
• Split graphs

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

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

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

  2003cited by this paper
• The On-Line Encyclopedia of Integer Sequences

  2003cited by this paper
• Finitely labeled generating trees and restricted permutations

  2003cited by this paper
• Longest Increasing Subsequences in Pattern-Restricted Permutations

  2003cited by this paper
• Restricted permutations and the wreath product

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

  2002cited by this paper
• 321-Polygon-Avoiding Permutations and Chebyshev Polynomials

  2002cited by this paper
• Ëóöøøòò Ûûøø Øûó Óöööööö ×øø Blockin× Ò ××ööö×

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

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

  2000cited by this paper
• Permutations with Restricted Patterns and Dyck Paths

  2000cited by this paper
• Continued Fractions and Catalan Problems

  2000cited by this paper
• Kazhdan-Lusztig Polynomials for 321-Hexagon-Avoiding Permutations

  2000cited by this paper
• On the Stanley-Wilf Conjecture for the Number of Permutations Avoiding a Given Pattern

  1999cited by this paper
• Restricted permutations

  1999cited by this paper
• Forbidden subsequences and Chebyshev polynomials

  1999cited by this paper
• Restricted Permutations, Continued Fractions, and Chebyshev Polynomials

  1999cited by this paper
• Permutation Patterns and Continued Fractions

  1999cited by this paper
• Permutations Containing and Avoiding Certain Patterns

  1999influential reference
• Enumerative Combinatorics: Index

  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

  1998cited by this paper
• Permutations, parenthesis words, and Schröder numbers

  1998cited by this paper
• Permutations which are the Union of an Increasing and a Decreasing Subsequence

  1998cited by this paper
• The Art of Computer Programming, Volume I: Fundamental Algorithms, 2nd Edition

  1997cited by this paper
• The art of computer programming: V.1.: Fundamental algorithms

  1997cited by this paper
• Generating trees and forbidden subsequences

  1996cited by this paper
• Partitioning Permutations into Increasing and Decreasing Subsequences

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

  1995influential reference
• Forbidden subsequences

  1994cited by this paper
• A k-Structure Generalization of the Theory of 2-Structures

  1994cited by this paper
• Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures

  1993cited by this paper
• Pattern Matching for Permutations

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

  1990cited by this paper
• Primitivity is Hereditary for 2-Structures

  1990cited by this paper
• Enumerative Combinatorics

  1986cited by this paper
• Algorithmic aspects of the substitution decomposition in optimization over relations, set systems and Boolean functions

  1985cited by this paper
• Substitution Decomposition for Discrete Structures and Connections with Combinatorial Optimization

  1984cited by this paper
• The art of computer programming

  1983influential reference
• What is an Answer

  1982cited by this paper
• Complement reducible graphs

  1981cited by this paper
• The Number of Baxter Permutations

  1977cited by this paper
• Enumeration of posets generated by disjoint unions and ordinal sums

  1974cited by this paper
• On well-quasi-ordering infinite trees

  1963cited by this paper
• Annals of Combinatorics

  year unknowncited by this paper
• Combinatory Analysis

  year unknowninfluential reference
• Séminaire Lotharingien de Combinatoire 47 (2002), Article B47c RESTRICTED PERMUTATIONS AND CHEBYSHEV POLYNOMIALS

  year unknowncited by this paper

• Combinatorial Exploration: An Algorithmic Framework for Enumeration

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

  2021influential citation
• FLEXIBLE SCHEMES AND BEYOND: EXPERIMENTAL ENUMERATION OF PATTERN AVOIDANCE CLASSES

  2020influential citation
• Flexible Schemes

  2019influential citation
• Flexible Schemes for Pattern-Avoiding Permutations

  2019influential citation
• Efficient solution of nonlinear model predictive control by a restricted enumeration method

  2018cites this paper
• What is an answer? - remarks, results and problems on PIO formulas in combinatorial enumeration, part I

  2018cites this paper
• Probability and Computing

  2018cites this paper
• Counting Permutations that Avoid Many Patterns

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

  2017influential citation
• Permutation patterns are hard to count

  2016cites this paper
• Experimental methods in permutation patterns and bijective proof

  2016cites this paper
• PENGEMBANGAN BAHAN AJAR MATERI ATURAN PENCACAHAN MENGGUNAKAN PEMBELAJARAN BERBASIS MASALAH DI SMA

  2015cites this paper
• Pattern avoidance is not P-recursive

  2015cites this paper
• On the growth of permutation classes

  2015cites this paper
• P-Recursive Integer Sequences and Automata Theory

  2015cites this paper
• Pattern avoidance in the rook monoid

  2014cites this paper
• Pattern Avoidance in Ordered Set Partitions

  2014cites this paper
• Refining Enumeration Schemes to Count According to Permutation Statistics

  2014influential citation
• Permutation Pattern Avoidance and the Catalan Triangle

  2013influential citation
• Fast Combinatorial Programs Generating Total Data

  2013cites this paper
• Approaches for enumerating permutations with a prescribed number of occurrences of patterns

  2013cites this paper
• The number of {1243, 2134}-avoiding permutations

  2013cites this paper
• Computational methods in permutation patterns

  2013cites this paper
• An algorithm for deciding the finiteness of the number of simple permutations in permutation classes

  2013cites this paper
• NSF Proposal: Automated Enumerative Combinatorics Automated Enumerative Combinatorics

  2013cites this paper
• Combinatorial specification of permutation classes

  2012cites this paper
• Sorting Permutations with Finite-Depth Stacks

  2012cites this paper
• Pattern Avoidance in Ordered Set Partitions

  2012influential citation
• Enumeration of Pin-Permutations

  2011cites this paper
• Algorithms for permutation statistics

  2011influential citation
• Enumeration schemes for vincular patterns

  2011influential citation
• REFINING ENUMERATION SCHEMES TO COUNT ACCORDING TO INVERSION NUMBER

  2010influential citation
• Enumeration schemes for words avoiding permutations

  2010cites this paper
• Enumeration Schemes for Permutations Avoiding Barred Patterns

  2010cites this paper
• Deciding the finiteness of the number of simple permutations contained in a wreath-closed class is polynomial

  2010cites this paper
• Re ning enumeration schemes to count according to the inversion number

  2010influential citation
• Counting 1324, 4231-Avoiding Permutations

  2009cites this paper
• Restricted k-ary words and functional equations

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

  2008influential citation
• Posets and permutations in the duplication-loss model: Minimal permutations with d descents

  2008cites this paper
• Overview of some general results in combinatorial enumeration

  2008influential citation
• Enumeration schemes for words avoiding patterns with repeated letters

  2008cites this paper
• Maximally Clustered Elements and Schubert Varieties

  2007cites this paper
• Enumeration of Some Classes of Words Avoiding Two Generalized Patterns of Length Three

  2007cites this paper
• The Enumeration of Maximally Clustered Permutations

  2007influential citation
• Embedded Factor Patterns for Deodhar Elements in Kazhdan-Lusztig Theory

  2006cites this paper
• Vincent Vatter — Project Description

  2006cites this paper