Permutation Pattern

👁 DOWNLOAD Mathematica Notebook
Download Wolfram Notebook

Let 👁 F(n,sigma)
denote the number of permutations on the symmetric group 👁 S_n
which avoid 👁 sigma in S_k
as a subpattern, where "👁 tau
contains 👁 sigma
as a subpattern" is interpreted to mean that there exist 👁 1<=x_1<=x_2<=...<=x_k<=n
such that for 👁 1<=i,j<=k
,

iff 👁 sigma(i)<sigma(j)
.

For example, a permutation contains the pattern (123) iff it has an ascending subsequence of length three. Here, note that members need not actually be consecutive, merely ascending (Wilf 1997). Therefore, of the 👁 3!=6
partitions of 👁 {1,2,3}
, all but 👁 {3,2,1}
(i.e., 👁 {1,2,3}
, 👁 {1,3,2}
, 👁 {2,1,3}
, 👁 {2,3,1}
, and 👁 {3,1,2}
) contain the pattern (12) (i.e., an increasing subsequence of length two).

The following table gives the numbers of pattern-matching permutations of 👁 k
, 👁 k+1
, ..., 👁 n
numbers for various patterns 👁 (a_1...a_k)
of length 👁 k
.

The following table gives the numbers of pattern-avoiding permutations of 👁 {1,...,n}
for various sets of patterns.

Abbreviations used in the above table are summarized below.

See also

Contained Pattern, Order Isomorphic, Permutation, Stanley-Wilf Conjecture, Wilf Class, Wilf Equivalent

Explore with Wolfram|Alpha

References

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.Billey, S.; Jockusch, W.; and Stanley, R. P. "Some Combinatorial Properties of Schubert Polynomials." J. Alg. Combin. 2, 345-374, 1993.Guibert, O. "Permutations sans sous séquence interdite." Mémoire de Diplô me d'Etudes Approfondies de L'Université Bordeaux I. 1992.Mansour, T. "Permutations Avoiding a Pattern from 👁 S_k
and at Least Two Patterns from 👁 S_3
." 31 Jul 2000. http://arxiv.org/abs/math.CO/0007194.Simon, R. and Schmidt, F. W. "Restricted Permutations." Europ. J. Combin. 6, 383-406, 1985.Sloane, N. J. A. Sequences A000027/M0472, A000071/M1056, A000073/M1074, A000108/M1459, A000124/M1041, A000142/M1675, A004275, A033312, and A056986, A158005, and A158006 in "The On-Line Encyclopedia of Integer Sequences."Stankova, Z. E. "Forbidden Subsequences." Disc. Math. 132, 291-316, 1994.West, J. "Generating Trees and Forbidden Subsequences." Disc. Math. 157, 363-372, 1996.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

Permutation Pattern

Cite this as:

Weisstein, Eric W. "Permutation Pattern." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/PermutationPattern.html

Subject classifications