階乗
概要
$0$ 以上の整数 $n$ について、$n$ の階乗 $n!$ とは、$n\times (n-1) \times \ldots \times 1$ の値のことを指す。
厳密な定義
厳密には、つぎのように定義される。
$0$ 以上の整数の集合を $\mathbb{N}_0$ と表記する。このとき、$!\colon \mathbb{N}_0\to \mathbb{N}_0$ を、以下に述べる性質が成り立つような唯一の関数として定める。
- $!(0)=1$
- $1\leq n$ について、$!(n)=n\times !(n-1)$
このとき、$n\in \mathbb{N}_0$ について $!(n)\in \mathbb{N}_0$ を $n$ の階乗 (factorial) とよぶ。また $!(n)$ について、一般的にはこれを $n!$ と表記する。
例
- $0!=1$.
- $1!=1\times 0!=1$.
- $2!=2\times 1!=2$.
- $3!=3\times 2!=6$.
- $10!=10\times 9\times 8\times 7\times 6\times 5\times 4\times 3\times 2\times 1\times 0!=3628800$.
増大性
計算を行うと、非負整数 $n$ に比べて $n!$ の値は非常に大きいことがわかる。実際、以下の定理が成り立つ。
任意の(整数係数)多項式関数 $F\colon\mathbb{N}_0\to \mathbb{Z}$ について、以下の条件を満たすような非負整数 $N$ が存在する。
- $N\lt n$ なる任意の非負整数 $n$ について、$F(n)\lt n!$
Abelの総和公式から、より正確な近似式が得られる。
$$\log(N!)=N\log N-\int_1^N \frac{\floor{t}}{t} dt=N\log N-N+\int_1^N\frac{\{t\}}{t} dt$$ となるので
$$N\log N-N<\log(N!)< N\log N-N+\log N$$ つまり
$$\left(\frac{N}{e}\right)^N< N!< N\left(\frac{N}{e}\right)^N$$ となることがわかる。
さらに強く、Stirlingの漸近公式
$$N!\sim \sqrt{2\pi N}\left(\frac{N}{e}\right)^N\left(1+\frac{1}{12N}+\frac{1}{288N^2}-\frac{139}{51840N^3}\cdots\right)$$ が成り立つ。単純な近似式として、
$$\sqrt{2\pi N}\left(\frac{N}{e}\right)^N e^{1/12(N+1)}< N!<\sqrt{2\pi N}\left(\frac{N}{e}\right)^N e^{1/12N}$$ となることが知られている (Robbins Rob)。
素因数分解
正の整数 $n>0$ の階乗 $n!$ の素因数分解を求める。
$1, 2, \ldots, n$ のうち、$p^k$ の倍数は
$$\floor{\frac{n}{p^k}}$$ 個あるから、
$1, 2, \ldots, n$ のうち、$p$ でちょうど $k$ 回割り切れるものの個数は
$$\floor{\frac{n}{p^k}}-\floor{\frac{n}{p^{k+1}}}$$ で与えられる。よって 素数 $p$ が $n!$ を割り切る回数は
$$\begin{split}
\sum_{k\geq 1} k\left(\floor{\frac{n}{p^k}}-\floor{\frac{n}{p^{k+1}}}\right)
= & \floor{\frac{n}{p}}-\floor{\frac{n}{p^2}}+2\left(\floor{\frac{n}{p^2}}-\floor{\frac{n}{p^3}}\right)+\cdots \\
= & \floor{\frac{n}{p}}+\floor{\frac{n}{p^2}}+\floor{\frac{n}{p^3}}+\cdots
\end{split}$$ と一致する。$p^k>n$ のとき、$\floor{n/p^k}=0$ となるから、2行目は有限和となる。A. M. Legendreが示した（Dickson Dic による）ことから、Legendreの公式という。
複素数への拡張
$\Gamma$ 関数は、階乗を取る操作のある種の一般化について述べているとみなすことができる。
$\Gamma$ 関数とは、正則関数 $\Gamma\colon\mathbb{C}\setminus \{0,-1,-2,\ldots\} \to \mathbb{C}$ であって、以下の条件を満たすものである。
- $\Gamma(1)=1$
- 複素数 $z$ について、$\Gamma(z+1)=z\Gamma(z)$
基数への拡張
このセクションにおいて、$\{i\in\mathbb{N}\mid i< n\}$ の略記として $n$ と表記する。また、$\mathrm{card}(X)$ で集合 $X$ の濃度を表すものとする。
$n!$ は $\mathrm{card}(\mathrm{Aut}(n))$ と等しいことがわかる。このとき、基数 $\kappa$ に対しても同様に $\kappa !:=\mathrm{card}(\mathrm{Aut}(\kappa))$ と定めることができる。このように定めた $\kappa !$ は $\kappa$ が無限基数であるとき $2^\kappa$ と等しいことが知られている。
対称群の位数として
$n$ 元集合 $X$ を任意に取る。$X$ から $X$ への集合としての同型(全単射)全体の集合を $\mathrm{Aut}(X)$ とよぶと、$\mathrm{Aut}(X)$ は $n!$ 個の要素を持つ有限集合となる。
$\mathrm{Aut}(X)$ は合成を演算とする群としての構造を入れることができる。この方法によって作られる群のことを対称群という。対称群の群論的性質などの詳細についてはリンク先を参照されよ。
参考文献
素因数分解については G. H. Hardy and E. M. Wright HW1（日本語訳 HW2HW3） Chapter 22, Theorem 416, p. 454 を参考とした。
Stirlingの近似公式については、E. T. Whittaker and G. N. Watson WW を参考とした。
Robbins Rob は doi:10.2307/2308012 (JSTOR) より無料で閲覧可能。
