スターリング順列

組合せ数学において、k位のスターリング順列とは、多重集合1, 1, 2, 2, ..., k , k （1 からkまでの各値が2つずつ存在する）の順列であり、順列に現れる各値iについて、 iの2つの値の間にあるすべての値がiよりも大きいという追加の特性を持つ。例えば、3 位のスターリング順列は15通りある。

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。

k次のスターリング順列の数は、二重階乗(2 k − 1)で与えられます 。

スターリング順列は、スターリング数を含む有理式において係数として現れる特定の数が非負である ことを示すために、ゲッセルとスタンレー^{[ 1 ]によって導入された。具体的には、}${\textstyle \left\langle \!\left\langle {n \atop k}\right\rangle \!\right\rangle }$

${\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}}}}$

ここで、 は第二種スターリング数を表し、ゲッセルとスタンレーは、がちょうど上昇するの位数のスターリング順列の個数を数えることを証明しました。スターリング数とのこの関係から、「スターリング順列」という名前が付けられています。一方、 の数は第二種オイラー数と呼ばれます。 ${\displaystyle \left\{{n \atop k}\right\}}$ ${\textstyle \left\langle \!\left\langle {n \atop k}\right\rangle \!\right\rangle }$ ${\displaystyle n}$ ${\displaystyle k}$ ${\textstyle \left\langle \!\left\langle {n \atop k}\right\rangle \!\right\rangle }$

構築順序で辺がラベル付けされた平面木のオイラーツアーからのスターリング順列の構築

スターリング順列は、 k個の辺を持つ根付き平面木に葉を 1 つずつ追加していくことで構築できるシーケンスを記述するために使用できます。辺が挿入された順序で番号付けされている場合、木のオイラーツアー（木の辺を 2 倍にして各ノードの子を左から右の順にトラバースすることによって形成される）の数のシーケンスはスターリング順列です。逆に、すべてのスターリング順列は木の構築シーケンスを記述し、 iとラベル付けされた辺からルートに最も近い辺が、順列内のi個の値のペアを最も近く取り囲む値のペアを持つ辺になります。 ^{[ 2 ]}

スターリング順列は、各値が2つ以上存在する多重集合の順列に一般化されている。^{[ 3 ]}研究者らは、特定のパターンを回避するスターリング順列の数についても研究している。^{[ 4 ]}

参照

• ラングフォードペアリング、同じ多重集合の異なる種類の順列

参考文献

1. ゲッセル、アイラ;スタンレー、リチャード・P. (1978)、「スターリング多項式」、Journal of Combinatorial Theory、シリーズA、24 (1): 24– 33、doi : 10.1016/0097-3165(78)90042-0、MR  0462961。
2. Janson, Svante (2008)、「平面再帰木、スターリング順列、そして壷モデル」、第5回数学・計算機科学コロキウム、Discrete Math. Theor. Comput. Sci. Proc.、AI、Assoc. Discrete Math. Theor. Comput. Sci.、ナンシー、pp.  541– 547、arXiv : 0803.1129、Bibcode : 2008arXiv0803.1129J、MR 2508813 。
3. クリングスバーグ、ポール; シュマルツリート、シンシア (1990)、「スターリング順列を含む構成的全単射の族」、第21回南東部組合せ論、グラフ理論、コンピューティング会議議事録 (フロリダ州ボカラトン、1990年)、Congressus Numerantium、第78巻、pp.  11– 15、MR 1140465 。
4. Kuba, Markus; Panholzer, Alois (2012)、「パターン制限付きスターリング順列の列挙式」、離散数学、312 (21): 3179– 3194、doi : 10.1016/j.disc.2012.07.011、MR 2957938 。