二重階乗

数学における階乗類似の組合せ論的函数の一つとして、二重階乗（にじゅうかいじょう、英: double factorial）または半階乗 (semifactorial) n!! は、与えられた自然数 n に対し、1 から n まで n と同じ偶奇性を持つものだけを全て掛けた積を言う。すなわち、 n ! ! := ∏ k = 0 ⌈ n / 2 ⌉ − 1 ( n − 2 k ) = n ( n − 2 ) ( n − 4 ) ⋯ . {\displaystyle n!!:=\prod _{k=0}^{\lceil n/2\rceil -1}(n-2k)=n(n-2)(n-4)\cdots .} さらに n = 0 のときは、空積と見て 0!! ≔ 1 と定義する。 この定義に従えば、偶数 n に対する二重階乗は n ! ! = ∏ k = 1 n / 2 ( 2 k ) = n ( n − 2 ) ( n − 4 ) ⋯ 4 ⋅ 2 {\displaystyle n!!=\prod _{k=1}^{n/2}(2k)=n(n-2)(n-4)\cdots 4\cdot 2} で与えられ、また奇数 n に対しては n ! ! = ∏ k = 1 ( n + 1 ) / 2 ( 2 k − 1 ) = n ( n − 2 ) ( n − 4 ) ⋯ 3 ⋅ 1 {\displaystyle n!!=\prod _{k=1}^{(n+1)/2}(2k-1)=n(n-2)(n-4)\cdots 3\cdot 1} で与えられる。例えば 9!! = 9 × 7 × 5 × 3 × 1 = 945である。 二重階乗 n!! を階乗函数の二回反復 (n!)! と混同してはならない、両者は全く異なる値をとる。 Merserve (1948) (二重階乗記法を用いたおそらく最初の出版物) は、二重階乗はもともとウォリス積の導出において生じるある種の三角積分の表示を簡単にするために導入されたと述べる。二重階乗は超球の体積の式にも現れ、また数え上げ組合せ論において多くの応用を持つ。 奇数に対する二重階乗のことを奇階乗 (odd factorial) と呼ぶこともある。 二重階乗は通常の階乗の半分の因子しか含まないから、その値は階乗 n! の平方根程度からそう大きくなることはないし、明らかに階乗函数の二回反復 (n!)! と比べればはるかに小さい。 偶数 n = 2k (k ≥ 0) の二重階乗は階乗を用いて n ! ! = 2 k k ! {\displaystyle n!!=2^{k}k!} と表すことができ、また奇数 n = 2k − 1 (k ≥ 1) の二重階乗は n ! ! = ( 2 k ) ! 2 k k ! = n ! ( n − 1 ) ! ! {\displaystyle n!!={\frac {(2k)!}{2^{k}k!}}={\frac {n!}{(n-1)!!}}} となる。この式では最初の分母は (2k)!! に等しく、それが分子の余計な偶数因子を打ち消す。 奇数 n = 2k − 1 (k ≥ 1) に対する二重階乗は 2k の k-順列の言葉で ( 2 k − 1 ) ! ! = 2 k P k 2 k = ( 2 k ) k _ 2 k {\displaystyle (2k-1)!!={\frac {_{2k}P_{k}}{2^{k}}}={\frac {(2k)^{\underline {k}}}{2^{k}}}} と書くことができる。 二重階乗は数え上げ組合せ論などの状況において頻繁に生じるという事実に動機づけられる。例えば奇階乗 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) を見よ。 偶二重階乗は超八面体群（英語版）（超立方体の符号付き対称性または置換の群）の元の数を与える。 通常の階乗函数は（ガンマ函数に拡張して）各負の整数の位置に極を持ち、それらの数へ階乗を延長することは妨げられる。しかし奇数の二重階乗は、その漸化式 n ! ! = n × ( n − 2 ) ! ! {\textstyle n!!=n\times (n-2)!!} を逆に解いて n ! ! = ( n + 2 ) ! ! n + 2 {\displaystyle n!!={\frac {(n+2)!!}{n+2}}} と書くことにより、任意の負の奇数に延長することができる。この逆向きの漸化式を用いれば、−1!! = 1, −3!! = −1, −5!! = 1/3 などが計算でき、これ以降の（絶対値がより大きい）負の奇数に対して、その二重階乗は全て分数である。特に、正の奇数 n に対し ( − n ) ! ! × n ! ! = ( − 1 ) n − 1 2 × n {\displaystyle (-n)!!\times n!!=(-1)^{\frac {n-1}{2}}\times n} が言える。 偶数引数に対する二重階乗の先述の定義はさておいて、z が正の奇数のときの値が z ! ! = z ( z − 2 ) ⋯ ( 3 ) = 2 z − 1 2 ( z 2 ) ( z − 2 2 ) ⋯ ( 3 2 ) = 2 z − 1 2 Γ ( z 2 + 1 ) Γ ( 1 2 + 1 ) = 2 z + 1 π Γ ( z 2 + 1 ) = ( z 2 ) ! 2 z + 1 π {\displaystyle {\begin{aligned}z!!&=z(z-2)\cdots (3)=2^{\frac {z-1}{2}}\left({\frac {z}{2}}\right)\left({\frac {z-2}{2}}\right)\cdots \left({\frac {3}{2}}\right)\\&=2^{\frac {z-1}{2}}{\frac {\Gamma \left({\frac {z}{2}}+1\right)}{\Gamma \left({\frac {1}{2}}+1\right)}}={\sqrt {\frac {2^{z+1}}{\pi }}}\Gamma \left({\frac {z}{2}}+1\right)=\left({\frac {z}{2}}\right)!{\sqrt {\frac {2^{z+1}}{\pi }}}\end{aligned}}} と書けることに着目して、奇階乗の定義域をほとんどの実数または複素数に対して延長することができる。 この関係式に従えば、z が非負偶数値をとるときの z!! の値は ( 2 k ) ! ! := 2 π ∏ i = 1 k ( 2 i ) = 2 k k ! 2 π {\displaystyle (2k)!!:={\sqrt {\frac {2}{\pi }}}\prod _{i=1}^{k}(2i)=2^{k}k!{\sqrt {\frac {2}{\pi }}}} と再定義されることになる。この意味での 0!! の値は 0 ! ! = 2 π ≈ 0.797 884 5608 … {\textstyle 0!!={\sqrt {\frac {2}{\pi }}}\approx 0.797\,884\,5608\ldots } である。 式を見れば z!! が負の偶数を除く任意の複素数に対して定義されることが分かる。またこれを定義として、半径 R の n-次元超球の体積は V n = 2 ( 2 π ) n − 1 2 n ! ! R n {\displaystyle V_{n}={\frac {2(2\pi )^{\frac {n-1}{2}}}{n!!}}R^{n}} と表せる。 整数 n に対して ∫ 0 π 2 sin n ⁡ x d x = ∫ 0 π 2 cos n ⁡ x d x = ( n − 1 ) ! ! n ! ! × { 1 if  n  is odd π 2 if  n  is even . {\displaystyle \int _{0}^{\frac {\pi }{2}}\sin ^{n}x\,dx=\int _{0}^{\frac {\pi }{2}}\cos ^{n}x\,dx={\frac {(n-1)!!}{n!!}}\times {\begin{cases}1&{\text{if }}n{\text{ is odd}}\\{\frac {\pi }{2}}&{\text{if }}n{\text{ is even}}.\end{cases}}} 奇階乗の複素変数への延長を用いた場合には、 ∫ 0 π 2 sin n ⁡ x d x = ∫ 0 π 2 cos n ⁡ x d x = ( n − 1 ) ! ! n ! ! π 2 . {\displaystyle \int _{0}^{\frac {\pi }{2}}\sin ^{n}x\,dx=\int _{0}^{\frac {\pi }{2}}\cos ^{n}x\,dx={\frac {(n-1)!!}{n!!}}{\sqrt {\frac {\pi }{2}}}.} 二重階乗はより複雑な三角多項式の積分の評価にも利用できる。 奇数の二重階乗とガンマ函数は等式 ( 2 n − 1 ) ! ! = 2 n ⋅ Γ ( 1 2 + n ) π = ( − 2 ) n ⋅ π Γ ( 1 2 − n ) {\displaystyle (2n-1)!!=2^{n}\cdot {\frac {\Gamma ({\frac {1}{2}}+n)}{\sqrt {\pi }}}=(-2)^{n}\cdot {\frac {\sqrt {\pi }}{\Gamma ({\frac {1}{2}}-n)}}} で関係する。 ほかに奇数の二重階乗を含む等式として: ( 2 n − 1 ) ! ! = ∑ k = 1 n − 1 ( n k + 1 ) ( 2 k − 1 ) ! ! ( 2 n − 2 k − 3 ) ! ! , ( 2 n − 1 ) ! ! = ∑ k = 0 n ( 2 n − k − 1 k − 1 ) ( 2 k − 1 ) ( 2 n − k + 1 ) k + 1 ( 2 n − 2 k − 3 ) ! ! , ( 2 n − 1 ) ! ! = ∑ k = 1 n ( n − 1 ) ! ( k − 1 ) ! k ( 2 k − 3 ) ! ! . {\displaystyle {\begin{aligned}(2n-1)!!&=\sum _{k=1}^{n-1}{\binom {n}{k+1}}(2k-1)!!(2n-2k-3)!!,\\(2n-1)!!&=\sum _{k=0}^{n}{\binom {2n-k-1}{k-1}}{\frac {(2k-1)(2n-k+1)}{k+1}}(2n-2k-3)!!,\\(2n-1)!!&=\sum _{k=1}^{n}{\frac {(n-1)!}{(k-1)!}}k(2k-3)!!.\end{aligned}}} 定義 1 二重階乗が（一重の）階乗の概念を一般化するのと同じ仕方で、整数値多重階乗 (multiple factorial, multifactorial) あるいは「歩み」となる正整数 α を明示して α-重階乗、α-階乗 (α-factorial) 函数 n ! ( α ) = { n ⋅ ( n − α ) ! ( α )  if  n > 0 ; 1  if  − α < n ≤ 0 ; 0  otherwise.  {\displaystyle n!_{(\alpha )}={\begin{cases}n\cdot (n-\alpha )!_{(\alpha )}&{\text{ if }}n>0;\\1&{\text{ if }}-\alpha <n\leq 0;\\0&{\text{ otherwise. }}\end{cases}}} は二重階乗を一般化する。n! が負の整数に対して、および n!! が負の偶数に対してそれぞれ定義されないことと同じように、n!α は α の負の倍数において定義されない。 定義 2 また同様に、α の倍数より 1 大きい z における値が z ! ( α ) = z ( z − α ) ⋯ ( α + 1 ) = k ( z − 1 ) / α ( z α ) ( z − α α ) ⋯ ( α + 1 α ) = k ( z − 1 ) / α Γ ( z α + 1 ) Γ ( 1 α + 1 ) {\displaystyle z!^{(\alpha )}=z(z-\alpha )\cdots (\alpha +1)=k^{(z-1)/\alpha }\left({\frac {z}{\alpha }}\right)\left({\frac {z-\alpha }{\alpha }}\right)\cdots \left({\frac {\alpha +1}{\alpha }}\right)=k^{(z-1)/\alpha }{\frac {\Gamma ({\frac {z}{\alpha }}+1)}{\Gamma ({\frac {1}{\alpha }}+1)}}} となることに着目してほとんどの実数および複素数に対して定義域を延長できる。 ガンマ函数を用いた最後の式はもとと比べて非常に広く定義されるもので、この定義により z!(α) は負の実軸上にある k の負の倍数を除く任意の複素数に対して定義された函数と見なせる。そして「z ≡ 1 mod α なる整数 z に対しては z!(α) = z!(α) を満たす」という意味でこの二つの定義は両立する。 z!α がほとんどの複素数 z に対して延長できることに加え、α も任意の正実数値としてこの定義は意味を為す。さらに言えば、k = 1 のとき、定義される函数 Π(z) はパイ函数である。また k = 2 のときは、奇階乗の複素変数への拡張に一致する。