Metraipolis › archive › dc_f46d65111ce8

Stirling permutation — Wikipedia (en)

Source
Wikipedia (en)
Original
https://en.wikipedia.org/wiki/Stirling_permutation
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-07T18:26:36.910Z
SHA-256 of the archived text
71a890eee028153b6a6c852f4f308efc058563e62f820e5c12d1b7762593d5e2
Stable URL of this page
https://metraipolis.com/documento/dc_f46d65111ce8

How to cite

Stirling permutation — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Stirling_permutation (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_f46d65111ce8 (Metraipolis archive dc_f46d65111ce8, sha256 71a890eee028153b6a6c852f4f308efc058563e62f820e5c12d1b7762593d5e2)
BibTeX
@misc{dcf46d65111ce8,
  title = {Stirling permutation — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/Stirling_permutation},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_f46d65111ce8; sha256 71a890eee028153b6a6c852f4f308efc058563e62f820e5c12d1b7762593d5e2},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Stirling_permutation. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

In combinatorial mathematics, a Stirling permutation of order k is a permutation of the multiset 1, 1, 2, 2, ..., k, k (with two copies of each value from 1 to k) with the additional property that, for each value i appearing in the permutation, any values between the two copies of i are larger than i. For instance, the 15 Stirling permutations of order three are 1,1,2,2,3,3; 1,2,2,1,3,3; 2,2,1,1,3,3; 1,1,2,3,3,2; 1,2,2,3,3,1; 2,2,1,3,3,1; 1,1,3,3,2,2; 1,2,3,3,2,1; 2,2,3,3,1,1; 1,3,3,1,2,2; 1,3,3,2,2,1; 2,3,3,2,1,1; 3,3,1,1,2,2; 3,3,1,2,2,1; 3,3,2,2,1,1. The number of Stirling permutations of order k is given by the double factorial (2k − 1)!!. Stirling permutations were introduced by Gessel and Stanley in order to show that certain numbers appearing as coefficients in rational expressions involving Stirling numbers are non-negative. Specifically, letting the numbers ⟨ ⟨ n k ⟩ ⟩ {\textstyle \left\langle \!\left\langle {n \atop k}\right\rangle \!\right\rangle } be defined by ∑ m = 0 ∞ { n + m m } x m = ∑ k = 0 n ⟨ ⟨ n k ⟩ ⟩ x k + 1 ( 1 − x ) 2 n + 1 {\displaystyle \sum _{m=0}^{\infty }\left\{{n+m \atop m}\right\}x^{m}={\frac {\sum _{k=0}^{n}\left\langle \!\left\langle {n \atop k}\right\rangle \!\right\rangle x^{k+1}}{(1-x)^{2n+1}}}} where the { n k } {\displaystyle \left\{{n \atop k}\right\}} denote the Stirling numbers of the second kind, Gessel and Stanley proved that ⟨ ⟨ n k ⟩ ⟩ {\textstyle \left\langle \!\left\langle {n \atop k}\right\rangle \!\right\rangle } counts the number of Stirling permutations of order n {\displaystyle n} with exactly k {\displaystyle k} ascents. It is this connection to Stirling numbers which explains the name "Stirling permutations." Meanwhile, the numbers ⟨ ⟨ n k ⟩ ⟩ {\textstyle \left\langle \!\left\langle {n \atop k}\right\rangle \!\right\rangle } are called Eulerian numbers of the second order. Stirling permutations may be used to describe the sequences by which it is possible to construct a rooted plane tree with k edges by adding leaves one by one to the tree. For, if the edges are numbered by the order in which they were inserted, then the sequence of numbers in an Euler tour of the tree (formed by doubling the edges of the tree and traversing the children of each node in left to right order) is a Stirling permutation. Conversely every Stirling permutation describes a tree construction sequence, in which the next edge closer to the root from an edge labeled i is the one whose pair of values most closely surrounds the pair of i values in the permutation. Stirling permutations have been generalized to the permutations of a multiset with more than two copies of each value. Researchers have also studied the number of Stirling permutations that avoid certain patterns.

Tema degli esploratori: matematica e informatica teorica (deposito sistematico; categoria «Combinatorics»).
Fonte: Wikipedia in inglese, voce «Stirling permutation» — https://en.wikipedia.org/wiki/Stirling_permutation
Wikidata Q17103734: «type of permutation in combinatorial mathematics» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q17103734
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Stirling_permutation?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1304262999, consultata il 2026-10-07T17:55:03.377Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 4929b670da0c9a6e602f6f45761e0f077e7040ce3e9dcc2b922d77d5cd5fda1c