Wolfram Language Paclet Repository
Community-contributed installable additions to the Wolfram Language
Stirling permutation
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, the values between the two copies of i are larger than i. Wikipedia uses larger than i, whereas an example on the OEIS uses less than i. Both work. For instance, the 15 Stirling permutations of order three are
In[513]:=
 | StirlingPermutations |
Out[513]=
{{3,3,2,2,1,1},{2,3,3,2,1,1},{2,2,3,3,1,1},{2,2,1,3,3,1},{2,2,1,1,3,3},{3,3,1,2,2,1},{1,3,3,2,2,1},{1,2,3,3,2,1},{1,2,2,3,3,1},{1,2,2,1,3,3},{3,3,1,1,2,2},{1,3,3,1,2,2},{1,1,3,3,2,2},{1,1,2,3,3,2},{1,1,2,2,3,3}}
In[514]:=
FromDigits/@
[3]
 | StirlingPermutations |
Out[514]=
{332211,233211,223311,221331,221133,331221,133221,123321,122331,122133,331122,133122,113322,112332,112233}
In[515]:=
Row/@
[3]
| StirlingPermutations |
Out[515]=
{332211,233211,223311,221331,221133,331221,133221,123321,122331,122133,331122,133122,113322,112332,112233}
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 1978 to show that certain numbers (the numbers of Stirling permutations with a fixed number of descents) are non-negative. They chose this name because of a connection to certain polynomials defined from the Stirling numbers, which are in turn named after 18th-century Scottish mathematician James Stirling.
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 were 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 a left to ride 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.
In[1047]:=
| StirlingPermutationGraph |
Out[1047]=
In[1048]:=
GraphTree
[{1,2,6,6,2,4,4,1,3,3,5,5}]
| StirlingPermutationGraph |
Out[1048]=
All trees of order 3:
In[1051]:=
GridPartition
[#,PlotLabel#]&/@
[3],5,DividersAll
 | StirlingPermutationGraph |
| StirlingPermutations |
All trees of order 4:
In[1052]:=
GridPartition
[#,PlotLabel#]&/@
[4],5,DividersAll
| StirlingPermutationGraph |
| StirlingPermutations |
Examples of displaying Stirling permutations:
In[1055]:=
MulticolumnSort@
@3,5,Appearance"Horizontal"
 | StirlingPermutations |
Out[1055]=
{1,1,2,2,3,3} | {1,1,2,3,3,2} | {1,1,3,3,2,2} | {1,2,2,1,3,3} | {1,2,2,3,3,1} |
{1,2,3,3,2,1} | {1,3,3,1,2,2} | {1,3,3,2,2,1} | {2,2,1,1,3,3} | {2,2,1,3,3,1} |
{2,2,3,3,1,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} |
In[1057]:=
MulticolumnSort@
@4,3,Appearance"Horizontal"
| StirlingPermutations |
Out[1057]=
{1,1,2,2,3,3,4,4} | {1,1,2,2,3,4,4,3} | {1,1,2,2,4,4,3,3} |
{1,1,2,3,3,2,4,4} | {1,1,2,3,3,4,4,2} | {1,1,2,3,4,4,3,2} |
{1,1,2,4,4,2,3,3} | {1,1,2,4,4,3,3,2} | {1,1,3,3,2,2,4,4} |
{1,1,3,3,2,4,4,2} | {1,1,3,3,4,4,2,2} | {1,1,3,4,4,3,2,2} |
{1,1,4,4,2,2,3,3} | {1,1,4,4,2,3,3,2} | {1,1,4,4,3,3,2,2} |
{1,2,2,1,3,3,4,4} | {1,2,2,1,3,4,4,3} | {1,2,2,1,4,4,3,3} |
{1,2,2,3,3,1,4,4} | {1,2,2,3,3,4,4,1} | {1,2,2,3,4,4,3,1} |
{1,2,2,4,4,1,3,3} | {1,2,2,4,4,3,3,1} | {1,2,3,3,2,1,4,4} |
{1,2,3,3,2,4,4,1} | {1,2,3,3,4,4,2,1} | {1,2,3,4,4,3,2,1} |
{1,2,4,4,2,1,3,3} | {1,2,4,4,2,3,3,1} | {1,2,4,4,3,3,2,1} |
{1,3,3,1,2,2,4,4} | {1,3,3,1,2,4,4,2} | {1,3,3,1,4,4,2,2} |
{1,3,3,2,2,1,4,4} | {1,3,3,2,2,4,4,1} | {1,3,3,2,4,4,2,1} |
{1,3,3,4,4,1,2,2} | {1,3,3,4,4,2,2,1} | {1,3,4,4,3,1,2,2} |
{1,3,4,4,3,2,2,1} | {1,4,4,1,2,2,3,3} | {1,4,4,1,2,3,3,2} |
{1,4,4,1,3,3,2,2} | {1,4,4,2,2,1,3,3} | {1,4,4,2,2,3,3,1} |
{1,4,4,2,3,3,2,1} | {1,4,4,3,3,1,2,2} | {1,4,4,3,3,2,2,1} |
{2,2,1,1,3,3,4,4} | {2,2,1,1,3,4,4,3} | {2,2,1,1,4,4,3,3} |
{2,2,1,3,3,1,4,4} | {2,2,1,3,3,4,4,1} | {2,2,1,3,4,4,3,1} |
{2,2,1,4,4,1,3,3} | {2,2,1,4,4,3,3,1} | {2,2,3,3,1,1,4,4} |
{2,2,3,3,1,4,4,1} | {2,2,3,3,4,4,1,1} | {2,2,3,4,4,3,1,1} |
{2,2,4,4,1,1,3,3} | {2,2,4,4,1,3,3,1} | {2,2,4,4,3,3,1,1} |
{2,3,3,2,1,1,4,4} | {2,3,3,2,1,4,4,1} | {2,3,3,2,4,4,1,1} |
{2,3,3,4,4,2,1,1} | {2,3,4,4,3,2,1,1} | {2,4,4,2,1,1,3,3} |
{2,4,4,2,1,3,3,1} | {2,4,4,2,3,3,1,1} | {2,4,4,3,3,2,1,1} |
{3,3,1,1,2,2,4,4} | {3,3,1,1,2,4,4,2} | {3,3,1,1,4,4,2,2} |
{3,3,1,2,2,1,4,4} | {3,3,1,2,2,4,4,1} | {3,3,1,2,4,4,2,1} |
{3,3,1,4,4,1,2,2} | {3,3,1,4,4,2,2,1} | {3,3,2,2,1,1,4,4} |
{3,3,2,2,1,4,4,1} | {3,3,2,2,4,4,1,1} | {3,3,2,4,4,2,1,1} |
{3,3,4,4,1,1,2,2} | {3,3,4,4,1,2,2,1} | {3,3,4,4,2,2,1,1} |
{3,4,4,3,1,1,2,2} | {3,4,4,3,1,2,2,1} | {3,4,4,3,2,2,1,1} |
{4,4,1,1,2,2,3,3} | {4,4,1,1,2,3,3,2} | {4,4,1,1,3,3,2,2} |
{4,4,1,2,2,1,3,3} | {4,4,1,2,2,3,3,1} | {4,4,1,2,3,3,2,1} |
{4,4,1,3,3,1,2,2} | {4,4,1,3,3,2,2,1} | {4,4,2,2,1,1,3,3} |
{4,4,2,2,1,3,3,1} | {4,4,2,2,3,3,1,1} | {4,4,2,3,3,2,1,1} |
{4,4,3,3,1,1,2,2} | {4,4,3,3,1,2,2,1} | {4,4,3,3,2,2,1,1} |
In[1058]:=
Length
@#&/@Range[9]
 | StirlingPermutations |
Out[1058]=
{1,3,15,105,945,10395,135135,2027025,34459425}
In[1059]:=
numberofStirlingPermutations[1]=1;numberofStirlingPermutations[k_]:=(2k-1)numberofStirlingPermutations[k-1]numberofStirlingPermutations/@Range[15]
Out[1061]=
{1,3,15,105,945,10395,135135,2027025,34459425,654729075,13749310575,316234143225,7905853580625,213458046676875,6190283353629375}
In[1062]:=
ClearAll[veAdd,eTrees,postmanTour]veAdd[g_,opts:OptionsPattern[]]:=Module[{vl=VertexList[g],voc=VertexOutComponent[g,#,1]&/@VertexList[g],vc=VertexCount[g]},Flatten[Function[x,Graph[Insert[vl,vc,1+VertexIndex[g,#]],Append[EdgeList[g],First[x]vc],GraphLayout{"LayeredEmbedding","RootVertex"0},EdgeLabels{e_Placed[Last@e,{Left,"Middle"}]},opts]&/@x]/@voc]]eTrees[1,opts:OptionsPattern[]]:={Graph[{0,1},{01},opts]};eTrees[k_,opts:OptionsPattern[]]:=Flatten[veAdd[#,opts]&/@eTrees[k-1]]postmanTour[t_]:=Module[{ug=UndirectedGraph[t,Options[t]/.DirectedEdgeUndirectedEdge]},PropertyValue[{ug,#},EdgeLabels]〚1〛&/@Reverse[FindPostmanTour[ug]〚1〛]]