Permutation patterns

2026-08-17 Improve this page

#Permutation patterns

A permutation $\pi \in \symS_n$ is said to contain the pattern $\sigma \in \symS_k,$ if there is a subsequence of $\pi$ which is order-isomorphic to $\sigma.$ For example, $\pi = [1, 8, 5, 3, 7, 4, 6, 2]$ contains the pattern $[2,3,1]$ because the subsequence $3,6,2$ has the same relative order as $2,3,1.$

Example (A permutation in $\symS_8$ and the pattern 231).

The permutation matrices associated with $\pi = [1, 8, 5, 3, 7, 4, 6, 2]$ and $\sigma = [2,3,1].$ Here we see that $\pi$ contains the pattern $\sigma$ (there are other instances of this pattern in $\pi$).

$\, $ $ \bullet $ $ \, $ $ \, $ $ \, $ $ \, $ $ \, $ $ \,$ $ \, $ $ \, $ $ \, $ $ \, $ $ \bullet $ $ \, $ $ \, $ $ \,$ $ \, $ $ \, $ $ \, $ $ \, $ $ \, $ $ \, $ $ \odot $ $ \,$ $ \, $ $ \, $ $ \bullet $ $ \, $ $ \, $ $ \, $ $ \, $ $ \,$ $ \, $ $ \, $ $ \, $ $ \, $ $ \, $ $ \bullet $ $ \, $ $ \,$ $ \, $ $ \, $ $ \, $ $ \odot $ $ \, $ $ \, $ $ \, $ $ \,$ $ \, $ $ \, $ $ \, $ $ \, $ $ \, $ $ \, $ $ \, $ $ \odot$ $ \bullet $ $ \, $ $ \, $ $ \, $ $ \, $ $ \, $ $ \, $ $ \,$ $\, $ $ \bullet $ $ \,$ $ \bullet $ $ \, $ $ \,$ $ \, $ $ \, $ $ \bullet$

Example (Structure of 132-avoiding permutations).

The number of permutations in $\symS_n$ avoiding $132$ is given by the Catalan number $\frac{1}{n+1}\binom{2n}{n}.$ The structure of a permutation matrix avoiding the pattern $132$ can be seen in the figure below. The larger regions on the left and right are also $132$-avoiding.

Structure of a 132-avoiding permutation.

This structure explains why 132-avoiding permutations satisfy the recursion for Catalan numbers.

In [Vat19], the author studies possible growth rates for pattern-avoiding permutations. For a recent survey of some open problems regarding permutation patterns, see [Vat26]. R. Domagalski, S. Elizalde, J. Liang, Q. Minnich, B. E. Sagan, J. Schmidt, and A. Sietsema introduce cyclic pattern containment and avoidance [DELM+22]. The cyclic setting treats permutations up to rotation and leads to cyclic analogues of classical avoidance questions.

#Arrow patterns and shallow permutations

Arrow patterns are variants of permutation patterns designed to remember some information from cycle notation while still being checked through one-line notation. An arrow pattern consists of an ordinary pattern together with arrows between labels, and an occurrence must realize both the usual order-isomorphism and the corresponding arrows under the permutation map.

Y. Berman and B. E. Tenner introduced arrow patterns in their study of pattern-functions and shallow permutations [BT22]. Let $I(\pi)$ be the inversion number, let $T(\pi)$ be the reflection length, and let $D(\pi)=\sum_i |\pi_i-i|$ be the total displacement. The Diaconis–Graham inequalities say \[I(\pi)+T(\pi) \leq D(\pi) \leq 2I(\pi).\] A permutation is shallow if equality holds in the lower bound. These permutations can be characterized by pattern avoidance conditions in cycle form. Shallow permutations avoiding a classical pattern of length three were enumerated by K. Archer, A. Geary, and R. P. Laudone [AGL26].

K. Archer and R. P. Laudone initiated a systematic study of arrow-pattern avoidance, including arrow-Wilf equivalence and enumeration of several avoidance classes [AL26]. S. Fu and Z. Yang then studied simultaneous avoidance of a classical pattern of length $3$ and an arrow pattern of length $3,$ resolving three conjectures of Archer–Laudone [FY26].

#Direct sums and skew sums of permutations

Given $\pi \in \symS_m$ and $\sigma \in \symS_n,$ we define the direct sum and the skew sum of $\pi$ and $\sigma$ as \[\begin{aligned} \pi \oplus \sigma \coloneqq {}& [\pi_1,\dotsc,\pi_m,\sigma_1+m,\dotsc,\sigma_n+m] \in \symS_{m+n}, \\ \pi \ominus \sigma \coloneqq {}& [\pi_1+n,\dotsc,\pi_m+n,\sigma_1,\dotsc,\sigma_n] \in \symS_{m+n}. \end{aligned}\] Note that these operations are not commutative, but they are associative.

#Pattern-avoidance classes

Many important families of permutations are defined by pattern avoidance. Here are some of the most common ones:

Dominant (132-avoiding), counted by Catalan numbers A000108.
Vexillary (2143-avoiding), see A005802.
Grassmannian (at most one descent), see A000325.
Separable (avoids $2413$ and $3142$), see A006318.
Baxter (avoids $2\text{-}41\text{-}3$ and $3\text{-}14\text{-}2$), see A001181.
Fully commutative (321-avoiding), counted by Catalan numbers A000108.

For a comprehensive list including non-pattern-based families, see the named families of permutations page.

Bibliography

[AGL26]Kassie Archer, Aaron Geary and Robert P. Laudone. Pattern-avoiding shallow permutations. The Electronic Journal of Combinatorics, 33(1):P1.49, 2026.

.bib

@article{ArcherGearyLaudone2026,
  author = {Kassie Archer and Aaron Geary and Robert P. Laudone},
  title = {Pattern-avoiding shallow permutations},
  year = {2026},
  journal = {The Electronic Journal of Combinatorics},
  volume = {33},
  number = {1},
  pages = {P1.49},
  doi = {10.37236/13826}
}

[AL26]Kassie Archer and Robert P. Laudone. Arrow pattern avoidance in permutations: Structure and enumeration. arXiv:2603.04218, 2026.

.bib

@article{ArcherLaudone2026x,
  author = {Kassie Archer and Robert P. Laudone},
  title = {Arrow pattern avoidance in permutations: structure and enumeration},
  year = {2026},
  eprint = {2603.04218},
  url = {https://arxiv.org/abs/2603.04218},
  journal = {arXiv e-prints}
}

[BT22]Yosef Berman and Bridget Eileen Tenner. Pattern-functions, statistics, and shallow permutations. The Electronic Journal of Combinatorics, 29(4):P4.43, 2022.

.bib

@article{BermanTenner2022,
  author = {Yosef Berman and Bridget Eileen Tenner},
  title = {Pattern-functions, statistics, and shallow permutations},
  year = {2022},
  journal = {The Electronic Journal of Combinatorics},
  volume = {29},
  number = {4},
  pages = {P4.43},
  doi = {10.37236/10858}
}

[DELM+22]Rachel Domagalski, Sergi Elizalde, Jinting Liang, Quinn Minnich, Bruce E. Sagan, Jamie Schmidt and Alexander Sietsema. Cyclic pattern containment and avoidance. Advances in Applied Mathematics, 135:102320, 2022.

.bib

@article{DomagalskiElizaldeLiangMinnichSaganSchmidtSietsema2022,
  author = {Rachel Domagalski and Sergi Elizalde and Jinting Liang and
    Quinn Minnich and Bruce E. Sagan and Jamie Schmidt and Alexander Sietsema},
  title = {Cyclic pattern containment and avoidance},
  year = {2022},
  journal = {Advances in Applied Mathematics},
  volume = {135},
  pages = {102320},
  doi = {10.1016/j.aam.2022.102320},
  url = {https://doi.org/10.1016/j.aam.2022.102320},
  eprint = {2106.02534}
}

[FY26]Shishuo Fu and Zhenghe Yang. When arrow patterns meet classical patterns. arXiv:2607.04094, 2026.

.bib

@article{FuYang2026x,
  author = {Shishuo Fu and Zhenghe Yang},
  title = {When arrow patterns meet classical patterns},
  year = {2026},
  eprint = {2607.04094},
  url = {https://arxiv.org/abs/2607.04094},
  journal = {arXiv e-prints}
}

[Vat19]Vincent Vatter. Growth rates of permutation classes: From countable to uncountable. Proceedings of the London Mathematical Society, 119(4):960–997, May 2019.

.bib

@article{Vatter2019,
  doi = {10.1112/plms.12250},
  url2 = {https://doi.org/10.1112/plms.12250},
  year = {2019},
  month = may,
  publisher = {Wiley},
  volume = {119},
  number = {4},
  pages = {960--997},
  author = {Vincent Vatter},
  title = {Growth rates of permutation classes: from countable to uncountable},
  journal = {Proceedings of the London Mathematical Society}
}

[Vat26]Vincent Vatter. An assortment of problems in permutation patterns: Unimodality, equivalence, derangements, and sorting. arXiv:2602.16355, 2026.

.bib

@article{Vatter2026x,
Author = {Vincent Vatter},
Title = {An assortment of problems in permutation patterns: unimodality, equivalence, derangements, and sorting},
Year = {2026},
Eprint = {2602.16355},
  url = {https://arxiv.org/abs/2602.16355},
journal = {arXiv e-prints}
}