TOPICS
Search

Stanley-Wilf Conjecture

Stanley and Wilf conjectured (Bona 1997, Arratia 1999), that for every permutation pattern sigma, there is a constant c(sigma)<infty such that for all n,

F(n,sigma)<=[c(sigma)]^n.

A related conjecture stated that for every sigma, the limit

lim_(n->infty)[F(n,sigma)]^(1/n)

exists and is finite.

Arratia (1999) showed that these two conjectures are equivalent. The conjecture was proved by Marcus and Tardos (2004).

See also

Permutation Pattern

Explore with Wolfram|Alpha

References

Alon, N. and Friedgut, E. "On the Number of Permutations Avoiding a Given Pattern." J. Combin. Th. Ser. A. 89, 133-140, 2000.Arratia, R. "On the Stanley-Wilf Conjecture for the Number of Permutations Avoiding a Given Pattern." Electronic J. Combinatorics 6, No. 1, N1, 1-4, 1999. http://www.combinatorics.org/Volume_6/Abstracts/v6i1n1.html.Bona, M. "Exact and Asymptotic Enumeration of Permutations with Subsequence Conditions." Ph.D. thesis. Cambridge, MA: MIT, 1997.Bona, M. "The Solution of a Conjecture of Stanley and Wilf for All Layered Patterns." J. Combin. Th. Ser. A 85, 96-104, 1999.Marcus, A. and Tardos, G. "Excluded Permutation Matrices and the Stanley-Wilf Conjecture." J. Combin. Th. Ser. A. 107, 153-160, 2004.Wilf, H. "On Crossing Numbers, and Some Unsolved Problems." In Combinatorics, Geometry, and Probability: A Tribute to Paul Erdős. Papers from the Conference in Honor of Erdős' 80th Birthday Held at Trinity College, Cambridge, March 1993 (Ed. B. Bollobás and A. Thomason). Cambridge, England: Cambridge University Press, pp. 557-562, 1997.

Referenced on Wolfram|Alpha

Stanley-Wilf Conjecture

Cite this as:

Weisstein, Eric W. "Stanley-Wilf Conjecture." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Stanley-WilfConjecture.html

Subject classifications