14.5 階乗の近似
総和の閉形式を見つけるテクニックはいくつか示したものの、これまで総乗については何も議論してこなかった。しかし幸いにも、次に示すような総乗を扱うために全く新しいツール一式が必要になるわけではない:
\[ n! ::= \prod_{i=1}^{n} i \]
なぜなら、対数を取れば任意の総乗は総和になるからである。例えば次の関係が成り立つ:
\[ P = \prod_{i=1}^{n} f(i) \ \ \longrightarrow \ \ \ln P = \sum_{i=1}^{n} \ln f(i) \]
後は総和を閉形式に変形 (もしくは近似) し、それを \(e\) の肩に乗せて対数を打ち消せば答えが得られる。
この方法で階乗関数 \(n!\) を閉形式に変換してみよう。まず \(n!\) の対数を取ると、次の関係が分かる:
\[ \begin{aligned} \ln n! &= \ln (1 \cdot 2 \cdot 3 \cdots (n - 1) \cdot n) \\ &= \ln 1 + \ln 2 + \ln 3 + \cdots + \ln (n - 1) + \ln n \\ &= \sum_{i=1}^{n} \ln i \end{aligned} \]
残念ながら、この総和を閉形式で表す方法は知られていない。しかし、定理 14.3.2 を使って閉形式の上界および下界を得ることはできる。このために、次の定積分を計算する:
\[ \begin{aligned} \int_{1}^{n} \ln x \, dx &= \left. (\text{\large\mathstrut} x \ln x - x) \right|_{1}^{n} \\ &= n \ln n - n + 1 \end{aligned} \]
これと定理 14.3.2 から、次の不等式を得る:
\[ n \ln n - n + 1 \ \leq \ \sum_{i=1}^{n} \ln i\ \leq\ n \ln n - n + 1 + \ln n \]
各項の指数を取れば、\(n!\) の満たす不等式が分かる:
\[ \frac{n^{n}}{e^{n-1}} \leq n! \leq \frac{n^{n+1}}{e^{n-1}} \tag{14.24}\]
これは \(n!\) が常に \(n^{n}/e^{n-1}\) から \(n \cdot n^{n}/e^{n-1}\) の範囲に収まることを意味する。
離散数学で最も頻繁に利用される総乗はおそらく \(n!\) である。そのため、数学者は \(n!\) のさらに優れた閉形式の上界および下界をいくつも発見している。最も有用なものを次に示す。
全ての正整数 \(n\) で次の等式が成り立つ:
\[ n! = \sqrt{2 n \pi} \left( \frac{n}{e} \right)^{\! n} e^{\varepsilon(n)} \]
ここで \(\varepsilon(n)\) は次の不等式を満たす:
\[ \frac{1}{12n + 1} \leq \varepsilon (n) \leq \frac{1}{12n} \]
定理 14.5.1 は数学的帰納法で証明できる (ただし少し難しい) ほか、初等的な微積分だけを使った証明も多く知られている。本書では証明を省略する。
Stirling の公式から分かる重要な事実がいくつかある。第一に、\(\varepsilon (n)\) は常に正である。よって全ての正整数 \(n\) で次の不等式が成り立つ:
\[ n! > \sqrt{2 n \pi} \left( \frac{n}{e} \right)^{\! n} \tag{14.25}\]
第二に、\(n\) が大きくなるとき \(\varepsilon (n)\) は \(0\) に向かう。これは次の関係を意味する:
\[ n! \sim \sqrt{2 n \pi} \left( \frac{n}{e} \right)^{\! n} \tag{14.26}\]
これは驚異的な結果である。\(n!\) と漸近等価な閉形式の式に \(\pi\) と \(e\) が両方とも現れるなど、誰が予想できただろうか？
第三に、\(n\) が小さいときでも \(\varepsilon (n)\) は小さい。そのため、ほとんどの正整数 \(n\) に対する \(n!\) の優れた近似値が Stirling の公式によって提供される。例えば、\(n!\) の近似値として
\[ \sqrt{2 n \pi} \left( \frac{n}{e} \right)^{\! n} \]
がよく使われる。この近似と真の値との相対誤差は次の値より小さいことが保証されている:
\[ e^{\varepsilon (n)} \leq e^{1/12n} \]
この近似は \(n \geq 10\) なら真の値から \(1\%\) の範囲に収まり、\(n \geq 100\) なら真の値から \(0.1\%\) の範囲に収まる。
さらに正確な \(n!\) の近似が必要な場合は、上界と下界のどちらが必要かに応じて次の式を使用できる:
\[ \begin{aligned} \text{上界: } &\sqrt{2 n \pi} \left( \frac{n}{e} \right)^{\! n} e^{1/12n} \\ \text{下界: } &\sqrt{2 n \pi} \left( \frac{n}{e} \right)^{\! n} e^{1/(12n + 1)} \end{aligned} \]
両方の値は真の値との相対誤差が
\[ e^{\frac{1}{12n} - \frac{1}{12n + 1}} = e^{\frac{1}{144n^{2} + 12n}} \]
以下だと保証されている。この近似は \(n \geq 10\) なら真の値から \(0.01\%\) の範囲に収まり、\(n \geq 100\) なら真の値から \(0.0001\%\) の範囲に収まる。
これらの事実をリファレンスとして系 14.5.2 と表 \(\text{14.1}\) にまとめる。
次の不等式が成り立つ:
\[ n! < \sqrt{2 n \pi} \left( \frac{n}{e} \right)^{\! n} \cdot \begin{cases} 1.09 & n \geq 1 \text{ のとき}\\ 1.009 & n \geq 10 \text{ のとき}\\ 1.0009 & n \geq 100 \text{ のとき}\\ \end{cases} \]
\[ \def\arraystretch{1.2}\begin{array}{c|cccc} \text{近似} & n \geq 1 & n \geq 10 & n \geq 100 & n \geq 1000 \\ \hline \text{\huge\mathstrut} \sqrt{2 n \pi} \left( \frac{n}{e} \right)^{\! n} & < 10\% & < 1\% & < 0.1\% & < 0.001\% \\ \text{\huge\mathstrut} \sqrt{2 n \pi} \left( \frac{n}{e} \right)^{\! n} e^{1/12n} & < 1\% & < 0.01\% & < 0.0001\% & < 0.000001\% \end{array} \]
定理 14.5.1 から得られる \(n!\) の二つの近似に対する真の値からの差