TOPICS

# Permutation Pattern

Let denote the number of permutations on the symmetric group which avoid as a subpattern, where " contains as a subpattern" is interpreted to mean that there exist such that for ,

iff .

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 partitions of , all but (i.e., , , , , and ) contain the pattern (12) (i.e., an increasing subsequence of length two).

The following table gives the numbers of pattern-matching permutations of , , ..., numbers for various patterns of length .

 pattern OEIS number of pattern-matching permutations 1 A000142 1, 2, 6, 24, 120, 720, 5040, ... 12 A033312 1, 5, 23, 119, 719, 5039, 40319, ... A056986 1, 10, 78, 588, 4611, 38890, ... 1234 A158005 1, 17, 207, 2279, 24553, ... 1324 A158009 1, 17, 207, 2278, 24527, ... 1342 A158006 1, 17, 208, 2300, 24835, ...

The following table gives the numbers of pattern-avoiding permutations of for various sets of patterns.

 Wilf class OEIS number of pattern-avoiding permutations A000108 1, 2, 5, 14, 42, 132, ... 123, 132, 213 A000027 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ... 132, 231, 321 A000027 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ... 123, 132, 3214 A000073 1, 2, 4, 7, 13, 24, 44, 81, 149, ... 123, 132, 3241 A000071 1, 2, 7, 12, 20, 33, 54, 88, 143, ... 123, 132, 3412 A000124 1, 2, 4, 7, 11, 16, 22, 29, 37, 46, ... 123, 231, A004275 1, 2, 4, 6, 8, 10, 12, 14, 16, 18, ... 123, 231, A000124 1, 2, 4, 7, 11, 16, 22, 29, 37, 46, ... 123, 231, 4321 1, 2, 4, 6, 3, 1, 0, ... 132, 213, 1234 A000073 1, 2, 4, 7, 13, 24, 44, 81, 149, ... 213, 231, A000124 1, 2, 4, 7, 11, 16, 22, 29, 37, 46, ...

Abbreviations used in the above table are summarized below.

 abbreviation patterns in class 123, 132, 213, 232, 312, 321 1432, 2143, 3214, 4132, 4213, 4312 1234, 1243, 1324, 1342, 1423, 2134, 2314, 2341, 2413, 2431, 3124, 3142, 3241, 3412, 3421, 4123, 4231 1234, 1243, 1423, 1432

## See also

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

## Explore with Wolfram|Alpha

More things to try:

## 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 and at Least Two Patterns from ." 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 Web Resource. https://mathworld.wolfram.com/PermutationPattern.html