階乗

同義語：factorial

概要

前提知識: 自然数, 数学的帰納法, 素数

定義

階乗

非負整数 $n$ の階乗（factorial）を $n!$ と書き、次の有限積で定義する。
$$n!=\prod_{j=1}^{n}j=1\cdot2\cdots n.$$
$n=0$ のときは空積を $1$ とする。

再帰式

階乗は次の初期値と再帰式を満たす。
$$0!=1,\qquad (n+1)!=(n+1)\,n!\quad(n\geq0).$$
この初期値と再帰式を満たす非負整数上の関数は一意である。

再帰式の証明

有限積の末尾の因子を取り出せば再帰式が得られる。
初期値が等しい二つの関数の $n$ での値が等しければ、再帰式から $n+1$ での値も等しい。
したがって数学的帰納法により一意性が従う。

具体値

$$0!=1,\quad1!=1,\quad2!=2,\quad3!=6,\quad4!=24,\quad5!=120,\quad10!=3628800.$$
$0!=1$ は $0$ を因子に持つ積の値ではなく、因子を一つも持たない積の約束である。

段階を一つ進めるたびに新しい整数を掛けるため、階乗の増大には一定の倍率の掛け算を繰り返す場合とは異なる速さが現れる。

二重階乗

非負整数 $n$ の二重階乗 $n!!$ を、$n$ と同じ偶奇の正整数を $n$ から $1$ または $2$ まで掛け合わせた積として定める。
$$(2m)!!:=\prod_{j=1}^{m}(2j)=2\cdot4\cdots(2m),\qquad(2m-1)!!:=\prod_{j=1}^{m}(2j-1)=1\cdot3\cdots(2m-1),\qquad0!!:=1 .$$

二重階乗と階乗の関係

正整数 $m$ に対し、次が成り立つ。
$$(2m)!!=2^m\,m!,\qquad(2m-1)!!=\frac{(2m)!}{2^m\,m!},\qquad(2m)!!\,(2m-1)!!=(2m)!.$$

二重階乗と階乗の関係の証明

各因子 $2j$ から $2$ を括り出すと $(2m)!!=2^m\prod_{j=1}^mj=2^m\,m!$ である。
$1$ から $2m$ までの整数は偶数 $2j$ と奇数 $2j-1$（$1\le j\le m$）に分かれるので $(2m)!=(2m)!!\,(2m-1)!!$ であり、これを $(2m)!!=2^mm!$ で割れば残る等式を得る。

似た記号との区別

二重階乗の例 $4!!=4\cdot2=8$ は、$4!=24$ と異なる。
また $(4!)!$ は $24!$ を表すので、$4!!$ と異なる。

公式と成立条件

固定次数の多項式との比較

固定した非負整数 $k$ に対して、次が成り立つ。
$$\lim_{n\to\infty}\frac{n!}{n^k}=+\infty.$$
したがって実係数多項式 $F$ に対して、十分大きい整数 $n$ では $F(n)< n!$ となる。

多項式との比較の証明

$n\geq2(k+1)$ なら末尾の $k+1$ 個の因子はそれぞれ $n/2$ 以上であり、残りの因子は $1$ 以上である。
$$\frac{n!}{n^k}\geq\frac{(n/2)^{k+1}}{n^k}=\frac{n}{2^{k+1}}\longrightarrow+\infty.$$
$F(n)=\sum_{j=0}^{k}a_jn^j$ と書けば、$n\geq1$ に対して $|F(n)|\leq(\sum_{j=0}^{k}|a_j|)n^k$ である。
この評価と極限を合わせれば結論を得る。
零多項式については $n!>0$ から直接従う。

指数の固定が必要

$n\geq1$ に対しては $n!\leq n^n$ である。
各因子 $j$ が $n$ 以下だからである。
したがって固定した指数についての極限を、指数も $n$ とともに変わる式へそのまま適用することはできない。
また $0!=1!$ なので、非負整数全体で階乗が狭義単調増加するとはいえない。

ここで $\log$ は自然対数を表す。

対数の積分表示

整数 $n\geq1$ に対して、$\{t\}=t-\lfloor t\rfloor$（$\lfloor t\rfloor$ は床関数）とおくと次が成り立つ。
$$\log(n!)=n\log n-\int_1^n\frac{\lfloor t\rfloor}{t}\,dt=n\log n-n+1+\int_1^n\frac{\{t\}}{t}\,dt.$$
整数 $n\geq2$ では、次の粗い両側評価が得られる。
$$e(n/e)^n< n!< en(n/e)^n.$$

積分表示の証明

各区間 $[j,j+1)$ で $\lfloor t\rfloor=j$ である。
$$\int_1^n\frac{\lfloor t\rfloor}{t}\,dt=\sum_{j=1}^{n-1}j\bigl(\log(j+1)-\log j\bigr)=n\log n-\log(n!).$$
最後の等式は、和を $\sum_{j=2}^{n}(j-1)\log j-\sum_{j=1}^{n-1}j\log j=(n-1)\log n-\sum_{j=2}^{n-1}\log j-\log 1$ と整理し、$\sum_{j=2}^{n-1}\log j=\log(n!)-\log n$ を用いれば得られる。
$\lfloor t\rfloor=t-\{t\}$ を代入すると、積分表示の後の等式が得られる。
$n=1$ では積分も空和も $0$ であり、同じ等式が成り立つ。
$n\geq2$ では $0<\int_1^n\{t\}/t\,dt<\int_1^n dt/t=\log n$ なので、指数関数を取ると両側評価を得る。

Robbins の評価

整数 $n\geq1$ に対して $A_n=\sqrt{2\pi n}(n/e)^n$ とおく。
Robbins の評価は次の形で与えられる（Rob55）。
$$A_n\exp\!\left(\frac{1}{12n+1}\right)< n!< A_n\exp\!\left(\frac{1}{12n}\right).$$
この精密評価は本記事では証明せず文献から採用する。

Stirling の公式

$n$ が正整数を通って無限大に向かうとき、次が成り立つ。
$$n!\sim\sqrt{2\pi n}\,(n/e)^n .$$
記号 $\sim$ は両辺の比が $1$ に収束することを表す（Landau記号）。

Robbins の評価からの導出

Robbins の評価の両辺を $A_n$ で割ると、両側の指数関数は $1$ に収束する。
はさみうちの原理により $n!/A_n\to1$ を得る。

Stirling の公式の証明の所在

上の導出は rem-factorial-robbins の評価に依存する。証明は Γ関数の記事（そこでの出典 Rud76・WW96）に譲る。

高次の補正

より細かい漸近展開の有限打切りとして、次がある（DLMF §5.11）。
$$n!=\sqrt{2\pi n}(n/e)^n\left(1+\frac{1}{12n}+\frac{1}{288n^2}-\frac{139}{51840n^3}+O(n^{-4})\right)\quad(n\to\infty).$$
これは誤差項を含む漸近式であり、括弧内を表示された多項式だけに置き換えた有限の $n$ での等式ではない。

性質

Legendre の公式

素数 $p$ と正整数 $M$ に対し、$v_p(M)$ を $p^e$ が $M$ を割り切る最大の非負整数 $e$ とする（p進付値）。
非負整数 $n$ に対して、次が成り立つ。
$$v_p(n!)=\sum_{r\geq1}\left\lfloor\frac{n}{p^r}\right\rfloor.$$
$p^r>n$ の項は $0$ なので、この和で非零となる項は有限個である。

Legendre の公式の証明

$n=0$ では $n!=1$ の付値も右辺も $0$ である。
$n\geq1$ では素因数分解の一意性から $v_p(n!)=\sum_{j=1}^n v_p(j)$ となる。
$v_p(j)$ は $p^r$ が $j$ を割り切る正整数 $r$ の個数に等しい。
有限個の組 $(j,r)$ を $r$ ごとに数え直すと、$p^r$ の倍数の個数は $\lfloor n/p^r\rfloor$ だから公式を得る。
別の数え方では、ちょうど $r$ 個の $p$ を因子に持つ整数の個数は $\lfloor n/p^r\rfloor-\lfloor n/p^{r+1}\rfloor$ である。
これに $r$ を掛けて $r\geq1$ で足す有限和も、隣り合う項の相殺により同じ右辺になる。

10の階乗の素因数

$$v_2(10!)=5+2+1=8,\qquad v_3(10!)=3+1=4,\qquad v_5(10!)=2,\qquad v_7(10!)=1.$$
したがって $10!=2^8\,3^4\,5^2\,7=3628800$ である。

この公式は階乗の付値を求めるものであり、二項係数の付値を直接述べる式とは区別する。公式の名称は Legendre に由来する（Dic05 Chapter IX）。

Wilson の定理

整数 $n\ge2$ について、$n$ が素数であることと $(n-1)!\equiv-1\pmod n$（合同式）は同値である。さらに $n$ が合成数のとき、$n=4$ ならば $(n-1)!\equiv2\pmod n$、$n\ne4$ ならば $(n-1)!\equiv0\pmod n$ である。

Wilson の定理の証明

$n=p$ を素数とする。$p=2$ では $1!=1\equiv-1\pmod2$ である。$p\ge3$ とする。$1\le a\le p-1$ なる各整数 $a$ は $p$ と互いに素なので、$ab\equiv1\pmod p$ となる $b$ が $1\le b\le p-1$ の範囲にただ一つ存在する（有限体 $\mathbb{Z}/p\mathbb{Z}$ の零でない元は可逆である）。$a$ 自身が自分の逆元になる、すなわち $a^2\equiv1$ となるのは、$p\mid(a-1)(a+1)$ から $a\equiv\pm1$、すなわち $a=1$ または $a=p-1$ のときに限る。残りの $p-3$ 個の整数 $2,\dots,p-2$ は、互いに逆元になる二つずつの組に分かれ、各組の積は $1$ と合同である。よって $(p-1)!\equiv1\cdot(p-1)\cdot1\equiv-1\pmod p$ である。
逆に $n$ を合成数とし、$n=ab$、$1< a\le b< n$ と書く。$a< b$ なら $a$ と $b$ は $1,\dots,n-1$ の相異なる因子なので $n\mid(n-1)!$ である。$a=b$、すなわち $n=a^2$ のとき、$a\ge3$ なら $2a< a^2=n$ なので $a$ と $2a$ が $(n-1)!$ の相異なる因子であり、$a\cdot2a=2n$ から $n\mid(n-1)!$ である。$a=2$ のときは $n=4$ で $3!=6\equiv2\pmod4$ である。いずれの場合も $(n-1)!\not\equiv-1\pmod n$ であり、同値性と合成数の場合の値が従う。

Wilson の定理の名称と歴史については HW08 §6.5（邦訳 HWJ22）を参照。

有限集合の対称群

$n$ 元集合の自己全単射の個数は $n!$ である（対称群）。
これは各元の像を重複なく順に選ぶと選択肢が $n,n-1,\ldots,1$ 個になることに対応する。
空集合の自己全単射は空写像一つなので、$n=0$ でも個数は $0!=1$ である。
自己全単射は写像の合成を演算として対称群をなす。
また $n$ 元集合の $k$ 元部分集合の個数 $\binom nk=n!/(k!(n-k)!)$ は階乗の比で表される（二項係数）。

計算と応用

Γ関数による複素変数への拡張

Γ関数は $\operatorname{Re}z>0$ でEuler積分により与えられる（DLMF §5.2）。
$$\Gamma(z)=\int_0^\infty t^{z-1}e^{-t}\,dt.$$
その解析接続は $D=\mathbb{C}\setminus\{0,-1,-2,\ldots\}$ 上で正則関数であり、$z\in D$ に対して $\Gamma(z+1)=z\Gamma(z)$ を満たす（DLMF §5.5）。
$\Gamma(1)=\int_0^\infty e^{-t}\,dt=1$ と再帰式から、非負整数 $n$ に対して $\Gamma(n+1)=n!$ となる。
正則性と初期値と再帰式だけでは、この関数を一意に特徴づけられない。
実際、$h(z)=e^{2\pi iz}\Gamma(z)$ も $D$ 上で正則である。
この関数は $h(1)=1$ を満たす。
さらに $h(z+1)=zh(z)$ が成り立つ。
しかし $h(1/2)=-\Gamma(1/2)\ne\Gamma(1/2)$ なので、$h$ は $\Gamma$ と異なる。
正の実数上で対数凸関数であることを課せば $\Gamma$ が一意に定まる（Bohr–Mollerup の定理、Γ関数）。

無限基数に対する別の拡張

集合 $X$ の自己全単射全体を $\operatorname{Sym}(X)$ と書き、基数 $\kappa=|X|$ に対して $\kappa!=|\operatorname{Sym}(X)|$ と定めることもある。
これは置換の個数を拡張する定義であり、Γ関数による複素変数への接続とは別である。
選択公理を用いる通常の基数演算の下で、無限基数 $\kappa$ について $\kappa!=2^\kappa$ となる。
上からは、各自己全単射のグラフ(写像)が $X\times X$ の部分集合であることと $|X\times X|=\kappa$ から $|\operatorname{Sym}(X)|\leq2^\kappa$ を得る。
下からは、$|X|=|X\times\{0,1\}|$ を用いて $X$ を $\kappa$ 個の二点組に分ける。
二点組の集合の各部分集合に対し、選ばれた組だけを交換する置換を対応させると、相異なる $2^\kappa$ 個の置換が得られる。
両側の不等式から等号が従う。
ここでは二点組への分割を含めて選択公理の下の無限基数の積の法則を用いている。
有限の場合には、例えば $2!=2\ne4=2^2$ であり、この等号は成立しない。