combinatorial mathematics Combinatorics is an area of mathematics primarily concerned with counting, both as a means and as an end to obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many a ...

, a Stirling permutation of order ''k'' is a

permutation In mathematics, a permutation of a set can mean one of two different things: * an arrangement of its members in a sequence or linear order, or * the act or process of changing the linear order of an ordered set. An example of the first mean ...

of the

multiset In mathematics, a multiset (or bag, or mset) is a modification of the concept of a set that, unlike a set, allows for multiple instances for each of its elements. The number of instances given for each element is called the ''multiplicity'' of ...

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 In mathematics, the double factorial of a number , denoted by , is the product of all the positive integers up to that have the same Parity (mathematics), parity (odd or even) as . That is, n!! = \prod_^ (n-2k) = n (n-2) (n-4) \cdots. Restated ...

(2''k'' − 1)!!. Stirling permutations were introduced by in order to show that certain numbers (the numbers of Stirling permutations with a fixed number of descents) are non-negative. They chose the name because of a connection to certain

polynomial In mathematics, a polynomial is a Expression (mathematics), mathematical expression consisting of indeterminate (variable), indeterminates (also called variable (mathematics), variables) and coefficients, that involves only the operations of addit ...

s defined from the

Stirling number In mathematics, Stirling numbers arise in a variety of Analysis (mathematics), analytic and combinatorics, combinatorial problems. They are named after James Stirling (mathematician), James Stirling, who introduced them in a purely algebraic setti ...

s, which are in turn named after 18th-century Scottish mathematician James Stirling. Stirling permutation Euler tour

Stirling permutations may be used to describe the sequences by which it is possible to construct a rooted

plane tree ''Platanus'' ( ) is a genus consisting of a small number of tree species native to the Northern Hemisphere. They are the sole living members of the family Platanaceae. All mature members of ''Platanus'' are tall, reaching in height. The type ...

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 In graph theory, an Eulerian trail (or Eulerian path) is a trail in a finite graph that visits every edge exactly once (allowing for revisiting vertices). Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail that starts and end ...

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..

References

{{reflist Permutations Combinatorics

See also

References