数え上げ組合せ論における応用

ウィキペディア小見出し辞書

数え上げ組合せ論における応用

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/06/20 19:02 UTC 版)

「二重階乗」の記事における「数え上げ組合せ論における応用」の解説

二重階乗は数え上げ組合せ論などの状況において頻繁に生じるという事実に動機づけられる。例えば奇階乗 n!! が現れる例としては: 奇数 n に対する完全グラフ Kn+1 の完全マッチング。そのようなグラフの任意の一つの頂点 v がマッチすることのできる頂点の選び方が n 通りで、選んだ残りは頂点数が 2 少ない完全グラフの完全マッチング問題に帰着される。例えば 4 = 3 + 1 頂点 a, b, c, d の完全グラフの完全マッチングは (ab, cd), (ac, bd), (ad, bc) で確かに 3!! = 3 通りであることが確認できる。 スターリング順列（英語版）: 同じ数が二つずつの多重集合 1, 1, 2, 2, …, k, k の置換（重複度まで込めてすべての元を一回ずつ用いる順列）で同じ数の各類はそれより大きい数によってのみ分けられるようにしたもの。で、k = n + 1/2 と置く。最も大きい k は二つとも隣り合うしかなく、それを取り除けば k − 1 を最大元とする順列が残るが、そのできた順列において隣り合う k が入れるのは n 通りの位置が考えられる。これで再帰的構成が得られたから、スターリング順列の数が二重順列で数えられることは帰納的にわかる。 あるいは同じ数の対の間に入れるのは大きい数だけという制約の代わりに、この多重集合の置換に現れる、同じ数の対のうち最初のほうは、あるきまった順番に並ぶという制約で考えることもできる。そのような順列が定めるのは、順列の 2k 箇所に関するマッチングであり、したがってふたたび個の順列の総数が二重階乗で数えられることがわかる ヒープの順序木: k + 1 個のノードが 0, 1, 2, …, k でラベル付けられた木で、ルートのラベルが 0 かつ、ほかのノードのラベルはその親ノードのラベルより大きく、各ノードの子ノードが決まった順になっている。この木のオイラー巡回（英語版） (Euler tour) はスターリング順列を与え、任意のスターリング順列はこの方法で木で表現できる 根なし二分木（英語版）で n + 5/2 個のラベル付き葉ノードを持つもの。そのような木の各々は、葉ノードが一つ少ない木から、n 本の辺の一つを細分して、新たな頂点を新たな葉ノードの親にすれば作れる。 根付き二分木（英語版）で n + 3/2 個のラベル付き葉ノードを持つもの。根なし木の場合と同様だが、細分できる辺の数は偶数で、辺の細分に加えて、二つの子がより小さい木および新たな葉ノードであるような新たな根を加えることにより、葉ノードが一つ少ない木にノードを加えることができる Callan (2009) および Dale & Moon (1993) は同様に二重階乗で数えられる組合せ論的数列（英語版）をさらにさまざまにリストしている: 例えば、「台形語」（"trapezoidal word": 奇数を含む複数の位取りの底を持つ混基数（英語版）記数法に属する数の体系）、高さでラベル付けられたダイク路（英語版）、高さでラベル付けられた順序木、"overhang path"、根付き二分木における各ノードに関する最小数付けられた葉ノードの降下列を記述するある種のベクトル、など。これらの対象のいくつかが同数であることを言う全単射による証明（英語版）（双射法）は Rubey (2008) および Marsh & Martin (2011) を見よ。 偶二重階乗は超八面体群（英語版）（超立方体の符号付き対称性または置換の群）の元の数を与える。