{{Short description|Type of permutation in combinatorial mathematics}} 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 (2''k'' − 1)!!.
Stirling permutations were introduced by Gessel and Stanley<ref>{{citation | last1 = Gessel | first1 = Ira | author1-link = Ira Gessel | last2 = Stanley | first2 = Richard P. | author2-link = Richard P. Stanley | doi = 10.1016/0097-3165(78)90042-0 | issue = 1 | journal = Journal of Combinatorial Theory | mr = 0462961 | pages = 24–33 | series = Series A | title = Stirling polynomials | volume = 24 | year = 1978| doi-access = free }}.</ref> in order to show that certain numbers appearing as coefficients in rational expressions involving Stirling numbers are non-negative. Specifically, letting the numbers <math display="inline"> \left\langle \! \left\langle {n \atop k} \right\rangle \! \right\rangle </math> be defined by :<math>\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}}</math> where the <math>\left\{ {n \atop k} \right\}</math> denote the Stirling numbers of the second kind, Gessel and Stanley proved that <math display="inline"> \left\langle \! \left\langle {n \atop k} \right\rangle \! \right\rangle </math> counts the number of Stirling permutations of order <math>n</math> with exactly <math>k</math> ascents. It is this connection to Stirling numbers which explains the name "Stirling permutations." Meanwhile, the numbers <math display="inline"> \left\langle \! \left\langle {n \atop k} \right\rangle \! \right\rangle </math> are called Eulerian numbers of the second order.
[[File:Stirling permutation Euler tour.svg|thumb|240px|Construction of a Stirling permutation from an Euler tour of a plane tree with its edges labeled by construction 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.<ref>{{citation | last = Janson | first = Svante | authorlink = Svante Janson | arxiv = 0803.1129 | contribution = Plane recursive trees, Stirling permutations and an urn model | mr = 2508813 | pages = 541–547 | publisher = Assoc. Discrete Math. Theor. Comput. Sci., Nancy | series = Discrete Math. Theor. Comput. Sci. Proc., AI | title = Fifth Colloquium on Mathematics and Computer Science | year = 2008| bibcode = 2008arXiv0803.1129J}}.</ref>
Stirling permutations have been generalized to the permutations of a multiset with more than two copies of each value.<ref>{{citation | last1 = Klingsberg | first1 = Paul | last2 = Schmalzried | first2 = Cynthia | contribution = A family of constructive bijections involving Stirling permutations | series = Congressus Numerantium | mr = 1140465 | pages = 11–15 | title = Proceedings of the Twenty-First Southeastern Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, Florida, 1990) | volume = 78 | year = 1990}}.</ref> Researchers have also studied the number of Stirling permutations that avoid certain patterns.<ref>{{citation | last1 = Kuba | first1 = Markus | last2 = Panholzer | first2 = Alois | doi = 10.1016/j.disc.2012.07.011 | issue = 21 | journal = Discrete Mathematics | mr = 2957938 | pages = 3179–3194 | title = Enumeration formulæ for pattern restricted Stirling permutations | volume = 312 | year = 2012| doi-access = free }}.</ref>
==See also== *Langford pairing, a different type of permutation of the same multiset
==References== {{reflist}}
Category:Permutations Category:Combinatorics