二重階乗
出典: フリー百科事典『ウィキペディア（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, 1, 2, 2, …, k, k の置換（重複度まで込めてすべての元を一回ずつ用いる順列）で同じ数の各類はそれより大きい数によってのみ分けられるようにしたもの。で、k = n + 1/2 と置く。最も大きい k は二つとも隣り合うしかなく、それを取り除けば k − 1 を最大元とする順列が残るが、そのできた順列において隣り合う k が入れるのは n 通りの位置が考えられる。これで再帰的構成が得られたから、スターリング順列の数が二重順列で数えられることは帰納的にわかる[1]。 あるいは同じ数の対の間に入れるのは大きい数だけという制約の代わりに、この多重集合の置換に現れる、同じ数の対のうち最初のほうは、あるきまった順番に並ぶという制約で考えることもできる。そのような順列が定めるのは、順列の 2k 箇所に関するマッチングであり、したがってふたたび個の順列の総数が二重階乗で数えられることがわかる[6]
- ヒープの順序木: k + 1 個のノードが 0, 1, 2, …, k でラベル付けられた木で、ルートのラベルが 0 かつ、ほかのノードのラベルはその親ノードのラベルより大きく、各ノードの子ノードが決まった順になっている。この木のオイラー巡回 (Euler tour) はスターリング順列を与え、任意のスターリング順列はこの方法で木で表現できる[1][8]
- 根なし二分木で n + 5/2 個のラベル付き葉ノードを持つもの。そのような木の各々は、葉ノードが一つ少ない木から、n 本の辺の一つを細分して、新たな頂点を新たな葉ノードの親にすれば作れる。
- 根付き二分木で n + 3/2 個のラベル付き葉ノードを持つもの。根なし木の場合と同様だが、細分できる辺の数は偶数で、辺の細分に加えて、二つの子がより小さい木および新たな葉ノードであるような新たな根を加えることにより、葉ノードが一つ少ない木にノードを加えることができる[1][6]
Callan (2009) および Dale & Moon (1993) は同様に二重階乗で数えられる組合せ論的数列をさらにさまざまにリストしている: 例えば、「台形語」（"trapezoidal word": 奇数を含む複数の位取りの底を持つ混基数記数法に属する数の体系）、高さでラベル付けられたダイク路、高さでラベル付けられた順序木、"overhang path"、根付き二分木における各ノードに関する最小数付けられた葉ノードの降下列を記述するある種のベクトル、など。これらの対象のいくつかが同数であることを言う全単射による証明（双射法）は Rubey (2008) および Marsh & Martin (2011) を見よ[9][10]。
偶二重階乗は超八面体群（超立方体の符号付き対称性または置換の群）の元の数を与える。
- ^ a b c d e f g h i Callan, David (2009). A combinatorial survey of identities for the double factorial. arXiv:0906.1317.
- ^ A000165
- ^ A001147
- ^ a b Meserve, B. E. (1948). “Classroom Notes: Double Factorials”. The American Mathematical Monthly 55 (7): 425–426. doi:10.2307/2306136. MR1527019.
- ^ a b Gould, Henry; Quaintance, Jocelyn (2012). “Double fun with double factorials”. Mathematics Magazine 85 (3): 177–192. doi:10.4169/math.mag.85.3.177. MR2924154.
- ^ a b c Dale, M. R. T.; Moon, J. W. (1993). “The permuted analogues of three Catalan sets”. Journal of Statistical Planning and Inference 34 (1): 75–87. doi:10.1016/0378-3758(93)90035-5. MR1209991.
- ^ 例えば Henderson, Daniel J.; Parmeter, Christopher F. (2012). “Canonical higher-order kernels for density derivative estimation”. Statistics & Probability Letters 82 (7): 1383–1387. doi:10.1016/j.spl.2012.03.013. MR2929790., Nielsen, B. (1999). “The likelihood-ratio test for rank in bivariate canonical correlation analysis”. Biometrika 86 (2): 279–288. doi:10.1093/biomet/86.2.279. MR1705359.
- ^ Janson, Svante (2008). “Fifth Colloquium on Mathematics and Computer Science”. Discrete Math. Theor. Comput. Sci. Proc., AI. Assoc. Discrete Math. Theor. Comput. Sci., Nancy. pp. 541–547
- ^ Rubey, Martin (2008). “20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008)”. Discrete Math. Theor. Comput. Sci. Proc., AJ. Assoc. Discrete Math. Theor. Comput. Sci., Nancy. pp. 691–704
- ^ Marsh, Robert J.; Martin, Paul (2011). “Tiling bijections between paths and Brauer diagrams”. Journal of Algebraic Combinatorics 33 (3): 427–453. arXiv:0906.0912. doi:10.1007/s10801-010-0252-6. MR2772541.
- ^ Hassani, Sadri (2000). Mathematical Methods: For Students of Physics and Related Fields. Undergraduate Texts in Mathematics. Springer. p. 266. ISBN 9780387989587
- ^ “Double factorial: Specific values (formula 06.02.03.0005)”. Wolfram Research (2001年10月29日). 2013年3月23日閲覧。
- ^ Mezey, Paul G. (2009). “Some dimension problems in molecular databases”. Journal of Mathematical Chemistry 45 (1): 1–6. doi:10.1007/s10910-008-9365-8.
- ^ Dassios, George; Kiriaki, Kiriakie (1987). “A useful application of Gauss theorem”. Bulletin de la Société Mathématique de Grèce 28 (part A): 40–43. MR935868.
- 二重階乗のページへのリンク
