On the number of permutations avoiding a given pattern
R. P. Stanley and H. Wilf [see, e.g., \textit{M. Bóna}, J. Comb. Theory, Ser. A 85, No. 1, 96-104 (1999; Zbl 0919.05002)] conjectured that for the number \(F(n,\sigma)\) of \(n\)-permutations avoiding (not containing) a given permutation \(\sigma\) there exists a constant \(c= c(\sigma)\) such that \(F(n,\sigma)\leq c^n\) for all \(n\). Using results about generalized Davenport-Schinzel sequences, the authors prove a slightly weaker statement: \(F(n,\sigma)\leq c^{n\gamma^*(n)}\), where \(\gamma^*(n)\) is an extremaly slowly growing function, related to the Ackermann hierarchy. They also prove that the conjecture holds for every permutation which consists of an increasing subsequence followed by a decreasing one, or vice versa.
- On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern
- The solution of a conjecture of Stanley and Wilf for all layered patterns
- Asymptotic enumeration of permutations avoiding generalized patterns
- Excluded permutation matrices and the Stanley-Wilf conjecture
- On the Stanley--Wilf limit of 4231-avoiding permutations and a conjecture of Arratia
- Asymptotic values for degrees associated with strips of Young diagrams
- Exact enumeration of 1342-avoiding permutations: A close link with labeled trees and planar maps
- Generalized Davenport-Schinzel sequences
- scientific article; zbMATH DE number 427792 (Why is no real title available?)
- scientific article; zbMATH DE number 732977 (Why is no real title available?)
- Permutations avoiding certain patterns: The case of length 4 and some generalizations
- Restricted permutations
- The solution of a conjecture of Stanley and Wilf for all layered patterns
- Restricted k-ary words and functional equations
- On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern
- Counting pattern-free set partitions. II: Noncrossing and other hypergraphs
- Shape avoiding permutations
- Avoidance of boxed mesh patterns on permutations
- Finite automata and pattern avoidance in words
- Quasirandom permutations
- Counting occurrences of a pattern of type (1, 2) or (2, 1) in permutations
- A simple proof for the exponential upper bound for some tenacious patterns
- On extremal permutations avoiding _N=NN-1 1
- Pattern occurrences in \(k\)-ary words revisited: a few new and old observations
- Permutations avoiding sets of patterns with long monotone subsequences
- On a conjecture about strong pattern avoidance
- Pattern avoidance over a hypergraph
- Stieltjes moment sequences for pattern-avoiding permutations
- Permutations all of whose patterns of a given length are distinct
- Forbidden paths and cycles in ordered graphs and matrices
- Counting occurrences of 231 in an involution
- On the Stanley--Wilf limit of 4231-avoiding permutations and a conjecture of Arratia
- Asymptotic enumeration of permutations avoiding generalized patterns
- Pattern avoidance in poset permutations
- Problems and conjectures presented at the problem session. Assembled by Vincent Vatter.
- scientific article; zbMATH DE number 5072523 (Why is no real title available?)
- A relation on 132-avoiding permutation patterns
- A probabilistic approach to consecutive pattern avoiding in permutations
- Degrees of nonlinearity in forbidden 0-1 matrix problems
- Permutation patterns are hard to count
- On the sub-permutations of pattern avoiding permutations
- On avoiding 1233
- The number of permutations avoiding a set of generalized permutation patterns
- Large deviations and ratio limit theorems for pattern-avoiding permutations
- Excluded permutation matrices and the Stanley-Wilf conjecture
- On permutation patterns with constrained gap sizes
- Strongly sublinear algorithms for testing pattern freeness
- Words over a finite alphabet avoiding 1243
- Extremal, enumerative and probabilistic results on ordered hypergraph matchings
- Avoiding consecutive patterns in permutations
This page was built for publication: On the number of permutations avoiding a given pattern
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1971017)
