Improve this page

#Named families of permutations

See the permutation patterns page for background on pattern containment and avoidance.

#Enumeration

The following table gives the number of permutations in each family in \(\symS_n.\) The entries are indexed by permutation size, even when the linked OEIS sequence uses a shifted index. For alternating permutations, the table counts either one of the two orientations.

Family OEIS 2 3 4 5 6 7 8 9 Alternating (one orientation) A000111 1 2 5 16 61 272 1385 7936 Ballot A000246 1 3 9 45 225 1575 11025 99225 Baxter A001181 2 6 22 92 422 2074 10754 58202 Bigrassmannian A050407 2 5 11 21 36 57 85 121 Boolean A001519 2 5 13 34 89 233 610 1597 Derangements A000166 1 2 9 44 265 1854 14833 133496 Dominant A000108 2 5 14 42 132 429 1430 4862 Fireworks A000110 2 5 15 52 203 877 4140 21147 Flattened A000110 1 2 5 15 52 203 877 4140 Fully commutative A000108 2 5 14 42 132 429 1430 4862 Grassmannian A000325 2 5 12 27 58 121 248 503 King A002464 0 0 2 14 90 646 5242 47622 Layered (Richardson) A000079 2 4 8 16 32 64 128 256 Parity-alternating A010551 1 2 4 12 36 144 576 2880 Separable A006318 2 6 22 90 394 1806 8558 41586 Simsun A000111 2 5 16 61 272 1385 7936 50521 Skew-merged A029759 2 6 22 86 340 1340 5254 20518 Vexillary A005802 2 6 23 103 513 2761 15767 94359 Wachs A359039 2 4 8 24 48 192 384 1920

#Definitions and characterizations

The families are listed alphabetically.

  • Alternating permutations come in two orientations. Up-down permutations have, in one-line notation, \(\pi_1 \lt \pi_2 \gt \pi_3 \lt \pi_4 \gt \dotsb.\) Down-up permutations have \(\pi_1 \gt \pi_2 \lt \pi_3 \gt \pi_4 \lt \dotsb.\) Each orientation is enumerated by the Euler numbers A000111. If both orientations are included, then for \(n\gt 1\) the count is twice an Euler number, as in A001250.

  • A permutation \(\pi\) is a ballot permutation if every prefix has no more descents than ascents; equivalently, for every \(j,\) \[\#\{i\lt{}j:\pi_i\gt{}\pi_{i+1}\} \leq \#\{i\lt{}j:\pi_i\lt{}\pi_{i+1}\}.\] The number of ballot permutations is given by A000246; see [LWZ22] for a decomposition and bijection with odd-order permutations.

  • Baxter — avoids the vincular patterns \(2\text{-}41\text{-}3\) and \(3\text{-}14\text{-}2,\) see [DG98] and A001181.

  • A permutation \(\pi\) is bigrassmannian if both \(\pi\) and \(\pi^{-1}\) are Grassmannian. The number of such permutations in \(\symS_n,\) including the identity, is \(1+\binom{n+1}{3}\); see A050407, with its index shifted by two.

  • Boolean — 321-avoiding and 3412-avoiding, see [Ten07, GPRT22]. A permutation is boolean if and only if the order ideal it defines in the Bruhat order is a Boolean lattice, see [Thm. 4.3, Ten07]. Enumerated by odd-indexed Fibonacci numbers, A001519.

  • Derangements — permutations with no fixed point, A000166.

  • Dominant — 132-avoiding. Enumerated by the Catalan numbers, A000108.

  • Fireworks — same as 3-12 avoiding, see [CS25]. This means that the initial terms of decreasing runs are increasing. Fireworks permutations are enumerated by the Bell numbers A000110.

  • Flattened permutations, where runs are in lex order. The flattened permutations in \(\symS_n\) are enumerated by the shifted Bell number \(B_{n-1}\); see A000110 and [Prop. 16, NRB20].

  • Fully commutative — 321-avoiding, see [BJS93, GPRT22]. Enumerated by the Catalan numbers, A000108.

  • A permutation is Grassmann (or Grassmannian) if it has at most one descent. These are special cases of vexillary permutations. There are \(2^n-n\) Grassmannian permutations in \(\symS_n\); see A000325. See the Schubert polynomial page for more details.

  • King permutations are permutations in which no two adjacent entries differ by \(1\) in one-line notation. This can be described via mesh-pattern avoidance, see A002464.

  • For a composition \((k_1,k_2,\dotsc,k_m)\) of \(n,\) the corresponding layered permutation, also called a Richardson permutation, is \[w_0^{(k_1)}\oplus w_0^{(k_2)}\oplus\dotsb\oplus w_0^{(k_m)},\] the direct sum of the longest permutations \(w_0^{(k_i)}\in\symS_{k_i}\); see [MS15]. Equivalently, layered permutations avoid both 231 and 312. There are \(2^{n-1}\) layered permutations in \(\symS_n,\) one for every composition of \(n\); see A000079.

  • Parity-alternating permutations are permutations satisfying \(\pi(i)\equiv i\pmod 2,\) see [KR21]. There are \(\lfloor n/2\rfloor!\,\lceil n/2\rceil!\) such permutations in \(\symS_n\); see A010551. This can be generalized to modulo-\(k\) alternating permutations, where we demand that \(\pi(i) \equiv i \pmod k.\) For pattern avoidance in modulo-\(k\) alternating permutations, see [AFGQ22].

  • Separable permutations are those which avoid \(2413\) and \(3142,\) see A006318. For reference, see [Wes95].

  • A simsun permutation is a permutation such that, after restricting to entries \(1,2,\dotsc,k,\) it does not have a double descent, that is, \(\pi(i)\gt \pi(i+1) \gt \pi(i+2),\) see [MY16]. The number of simsun permutations in \(\symS_n\) is the Euler number \(E_{n+1}\); see A000111.

  • Skew-merged permutations avoid \(2143\) and \(3412.\) These are exactly the ones formed as the union of an increasing sequence and a decreasing sequence; see [Thm. 2.9, Sta94], A029759. See [Atk98] for exact enumeration and connection with RSK.

  • A permutation is vexillary if it avoids the pattern 2143; see A005802.

  • Wachs permutations — A359039. These are the permutations in \(\symS_n\) defined as \[W_n \coloneqq \{\sigma\in\symS_n:|\sigma^{-1}(i)-\sigma^{-1}(i^*)|\leq 1 \text{ for all }i\in[n-1]\},\] where \(i^*\) is defined as \[i^* \coloneqq \begin{cases} i-1 &\text{if $i$ is even} \\ i+1 &\text{if $i$ is odd and $i+1 \leq n$} \\ n & \text{otherwise.} \end{cases}\] These permutations are studied in [BS24], and there are generalizations to other types.

Bibliography

  1. [AFGQ22]Per Alexandersson, Samuel Asefa Fufa, Frether Getachew and Dun Qiu. Pattern-avoidance and Fuss–Catalan numbers. arXiv:2201.08168, 2022.
    .bib
    @article{AlexanderssonFufaGetachewQiu2022x,
Author = {Per Alexandersson and Samuel Asefa Fufa and Frether Getachew and Dun Qiu},
Title = {Pattern-avoidance and {F}uss--{C}atalan numbers},
Year = {2022},
Eprint = {2201.08168},
  url = {https://arxiv.org/abs/2201.08168},
journal = {arXiv e-prints}
}
  2. [Atk98]M. D. Atkinson. Permutations which are the union of an increasing and a decreasing subsequence. The Electronic Journal of Combinatorics, 5(1), January 1998.
    .bib
    @article{Atkinson1998,
  title = {Permutations which are the union of an increasing and a decreasing subsequence},
  volume = {5},
  ISSN = {1077-8926},
  url = {http://dx.doi.org/10.37236/1344},
  DOI = {10.37236/1344},
  number = {1},
  journal = {The Electronic Journal of Combinatorics},
  publisher = {The Electronic Journal of Combinatorics},
  author = {Atkinson,  M. D.},
  year = {1998},
  month = jan 
}
  3. [BJS93]Sara C. Billey, William Jockusch and Richard P. Stanley. Some combinatorial properties of Schubert polynomials. Journal of Algebraic Combinatorics, 2(4):345–374, 1993.
    .bib
    @article{BilleyJockuschStanley1993,
  doi = {10.1023/a:1022419800503},
  url2 = {https://doi.org/10.1023/a:1022419800503},
  year = {1993},
  publisher = {Springer Nature},
  volume = {2},
  number = {4},
  pages = {345--374},
  author = {Sara C. Billey and William Jockusch and Richard P. Stanley},
  title = {Some Combinatorial Properties of {S}chubert Polynomials},
  journal = {Journal of Algebraic Combinatorics}
}
  4. [BS24]Francesco Brenti and Paolo Sentinelli. Wachs permutations, Bruhat order and weak order. European Journal of Combinatorics, 119:103804, 2024.
    .bib
    @article{BrentiSentinelli2022x,
  author = {Brenti, Francesco and Sentinelli, Paolo},
  title = {Wachs permutations, {B}ruhat order and weak order},
  year = {2024},
  journal = {European Journal of Combinatorics},
  volume = {119},
  pages = {103804},
  publisher = {Elsevier BV},
  doi = {10.1016/j.ejc.2023.103804},
  url = {https://doi.org/10.1016/j.ejc.2023.103804},
  eprint = {2212.04932}
}
  5. [CS25]Jack Chen-An Chou and Linus Setiabrata. Newton polytopes of fireworks Grothendieck polynomials. arXiv:2508.09107, 2025.
    .bib
    @article{ChouSetiabrata2025x,
  author = {Jack Chen-An Chou and Linus Setiabrata},
  title = {Newton polytopes of fireworks {G}rothendieck polynomials},
  year = {2025},
  eprint = {2508.09107},
  url = {https://arxiv.org/abs/2508.09107},
  journal = {arXiv e-prints}
}
  6. [DG98]S. Dulucq and O. Guibert. Baxter permutations. Discrete Mathematics, 180(1-3):143–156, 1998.
    .bib
    @article{DulucqGuibert1998,
  author = {S. Dulucq and O. Guibert},
  title = {Baxter permutations},
  journal = {Discrete Mathematics},
  volume = {180},
  number = {1-3},
  pages = {143--156},
  year = {1998},
  doi = {10.1016/S0012-365X(97)00112-X}
}
  7. [GPRT22]Emily Gunawan, Jianping Pan, Heather M. Russell and Bridget Eileen Tenner. RSK tableaux and the weak order on fully commutative permutations. arXiv:2212.05002, 2022.
    .bib
    @article{GunawanPanRussellTenner2022x,
Author = {Emily Gunawan and Jianping Pan and Heather M. Russell and Bridget Eileen Tenner},
Title = {RSK tableaux and the weak order on fully commutative permutations},
Year = {2022},
Eprint = {2212.05002},
  url = {https://arxiv.org/abs/2212.05002},
journal = {arXiv e-prints}
}
  8. [KR21]Frether Getachew Kebede and Fanja Rakotondrajao. Parity alternating permutations starting with an odd integer. Enumerative Combinatorics and Applications, 2021(2):Article #S2R16, March 2021.
    .bib
    @article{KebedeRakotondrajao2021,
  doi = {10.54550/eca2021v1s2r16},
  url2 = {https://doi.org/10.54550/eca2021v1s2r16},
  year = {2021},
  month = mar,
  publisher = {University of Haifa},
  volume = {2021},
  number = {2},
  pages = {Article {\#}S2R16},
  author = {Frether Getachew Kebede and Fanja Rakotondrajao},
  title = {Parity alternating permutations starting with an odd integer},
  journal = {Enumerative Combinatorics and Applications}
}
  9. [LWZ22]Zhicong Lin, David G. L. Wang and Tongyuan Zhao. A decomposition of ballot permutations, pattern avoidance and Gessel walks. Journal of Combinatorial Theory, Series A, 191:105644, 2022.
    .bib
    @article{LinWangZhao2022Ballot,
  author = {Zhicong Lin and David G. L. Wang and Tongyuan Zhao},
  title = {A decomposition of ballot permutations, pattern avoidance and
           {G}essel walks},
  year = {2022},
  journal = {Journal of Combinatorial Theory, Series A},
  volume = {191},
  pages = {105644},
  doi = {10.1016/j.jcta.2022.105644},
  eprint = {2103.04599},
  url = {https://arxiv.org/abs/2103.04599}
}
  10. [MY16]Shi-Mei Ma and Yeong-Nan Yeh. The peak statistics on simsun permutations. The Electronic Journal of Combinatorics, 23(2), April 2016.
    .bib
    @article{MaYeh2016,
  doi = {10.37236/5908},
  url2 = {https://doi.org/10.37236/5908},
  year = {2016},
  month = apr,
  publisher = {The Electronic Journal of Combinatorics},
  volume = {23},
  number = {2},
  author = {Shi-Mei Ma and Yeong-Nan Yeh},
  title = {The Peak Statistics on Simsun Permutations},
  journal = {The Electronic Journal of Combinatorics}
}
  11. [MS15]Grigory Merzon and Evgeny Smirnov. Determinantal identities for flagged Schur and Schubert polynomials. European Journal of Mathematics, 2(1):227–245, October 2015.
    .bib
    @article{MerzonSmirnov2015,
  doi = {10.1007/s40879-015-0078-9},
  url2 = {https://doi.org/10.1007/s40879-015-0078-9},
  year  = {2015},
  month = oct,
  publisher = {Springer Nature},
  volume = {2},
  number = {1},
  pages = {227--245},
  author = {Grigory Merzon and Evgeny Smirnov},
  title = {Determinantal identities for flagged {S}chur and {S}chubert polynomials},
  journal = {European Journal of Mathematics}
}
  12. [NRB20]Olivia Nabawanda, Fanja Rakotondrajao and Alex Samuel Bamunoba. Run distribution over flattened partitions. Journal of Integer Sequences, 23, 2020.
    .bib
    @article{NabawandaRakotondrajaoBamunoba2020,
Author = {Olivia Nabawanda and Fanja Rakotondrajao and Alex Samuel Bamunoba},
Title = {Run Distribution Over Flattened Partitions},
Year = {2020},
journal = {Journal of Integer Sequences},
volume = {23},
paper = {20.9.6},
issn = {1530-7638},
url = {https://cs.uwaterloo.ca/journals/JIS/VOL23/Nabawanda/naba5.html}
}
  13. [Sta94]Zvezdelina E. Stankova. Forbidden subsequences. Discrete Mathematics, 132(1–3):291–316, September 1994.
    .bib
    @article{Stankova1994,
  title = {Forbidden subsequences},
  volume = {132},
  ISSN = {0012-365X},
  url = {http://dx.doi.org/10.1016/0012-365X(94)90242-9},
  DOI = {10.1016/0012-365x(94)90242-9},
  number = {1–3},
  journal = {Discrete Mathematics},
  publisher = {Elsevier BV},
  author = {Stankova,  Zvezdelina E.},
  year = {1994},
  month = sep,
  pages = {291–-316}
}
  14. [Ten07]Bridget Eileen Tenner. Pattern avoidance and the Bruhat order. Journal of Combinatorial Theory, Series A, 114(5):888–905, July 2007.
    .bib
    @article{Tenner2007,
  doi = {10.1016/j.jcta.2006.10.003},
  url2 = {https://doi.org/10.1016/j.jcta.2006.10.003},
  year = {2007},
  month = jul,
  publisher = {Elsevier {BV}},
  volume = {114},
  number = {5},
  pages = {888--905},
  author = {Bridget Eileen Tenner},
  title = {Pattern avoidance and the {B}ruhat order},
  journal = {Journal of Combinatorial Theory,  Series A}
}
  15. [Wes95]Julian West. Generating trees and the Catalan and Schröder numbers. Discrete Mathematics, 146(1–3):247–262, November 1995.
    .bib
    @article{West1995,
  title = {Generating trees and the {C}atalan and {S}chröder numbers},
  volume = {146},
  ISSN = {0012-365X},
  url = {http://dx.doi.org/10.1016/0012-365X(94)00067-1},
  DOI = {10.1016/0012-365x(94)00067-1},
  number = {1–3},
  journal = {Discrete Mathematics},
  publisher = {Elsevier BV},
  author = {West,  Julian},
  year = {1995},
  month = nov,
  pages = {247–262}
}

I use cookies to detect website issues and track search terms.