Loading article…
組合せ数学において、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)!!で与えられる 。スターリング順列は、特定の数(固定数の降下を伴うスターリング順列の数)が非負であることを示すために、ゲッセルとスタンレー(1978)によって導入された。スターリング数から定義された特定の多項式との関連から、彼らはその名前を選んだ。スターリング数は、18世紀のスコットランドの数学者ジェームズ・スターリングにちなんで名付けられた。[1]
スターリング順列は、 k辺を持つルート付き平面木を、木に葉を 1 つずつ追加して構築できるシーケンスを記述するために使用できます。エッジが挿入された順序で番号付けされている場合、木のオイラー ツアー(木のエッジを 2 倍にして、各ノードの子を左から右の順にトラバースすることによって形成される) 内の番号のシーケンスはスターリング順列です。逆に、すべてのスターリング順列は、iとラベル付けされたエッジからルートに最も近い次のエッジが、順列内のiの値のペアに最も近い値のペアである木の構築シーケンスを記述します。[2]
スターリング順列は、各値が2つ以上存在する多重集合の順列に一般化されている。[3]研究者らは、特定のパターンを回避するスターリング順列の数についても研究している。[4]
参照
- ラングフォードペアリング、同じ多重集合の異なるタイプの順列
参考文献
- ^ ゲッセル、アイラ;スタンレー、リチャード P. (1978)、「スターリング多項式」、組み合わせ理論ジャーナル、シリーズ A、24 (1): 24–33、doi : 10.1016/0097-3165(78)90042-0、MR 0462961。
- ^ Janson, Svante (2008)、「平面再帰木、スターリング順列、壷モデル」、第 5 回数学およびコンピュータ サイエンス コロキウム、Discrete Math. Theor. Comput. Sci. Proc.、AI、Assoc. Discrete Math. Theor. Comput. Sci.、Nancy、pp. 541–547、arXiv : 0803.1129、Bibcode :2008arXiv0803.1129J、MR 2508813。
- ^ クリングスバーグ、ポール、シュマルツリード、シンシア (1990)、「スターリング順列を含む建設的全単射のファミリー」、第 21 回南東部組合せ論、グラフ理論、コンピューティングに関する会議議事録 (フロリダ州ボカラトン、1990 年)、Congressus Numerantium、第 78 巻、pp. 11–15、MR 1140465。
- ^ クバ、マルクス; パンホルツァー、アロイス (2012)、「パターン制限スターリング順列の列挙式」、離散数学、312 (21): 3179–3194、doi : 10.1016/j.disc.2012.07.011、MR 2957938。