階乗の増大度
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/05/18 08:10 UTC 版)
「スターリングの近似」も参照 n が増えるにつれて、階乗 n ! は n を変数とする任意の多項式函数あるいは指数函数よりも早く増加する（ただし、二重指数関数よりは遅い）。 n ! の近似式の多くは自然対数 log n ! = ∑ x = 1 n log x {\displaystyle \log n!=\sum _{x=1}^{n}\log x} であることを利用する。もっとも単純に得られる log(n!) の近似値を評価する式は、上記の式と以下の積分: ∫ 1 n log x d x ≤ ∑ x = 1 n log x ≤ ∫ 0 n log ( x + 1 ) d x {\displaystyle \int _{1}^{n}\log x\,dx\leq \sum _{x=1}^{n}\log x\leq \int _{0}^{n}\log(x+1)\,dx} によって与えられる。積分を評価すれば n log ( n e ) + 1 ≤ log n ! ≤ ( n + 1 ) log ( n + 1 e ) + 1 {\displaystyle n\log \left({\frac {n}{e}}\right)+1\leq \log n!\leq \left(n+1\right)\log \left({\frac {n+1}{e}}\right)+1} を得る。これは、ランダウの記号を用いれば log(n!) のオーダーは Θ(n log n) であることを言っているのであり、この結果はソートアルゴリズムの計算量を測るのに重要な役割を果たす。さて上記の log(n!) の評価から e ( n e ) n ≤ n ! ≤ e ( n + 1 e ) n + 1 {\displaystyle e\left({\frac {n}{e}}\right)^{n}\leq n!\leq e\left({\frac {n+1}{e}}\right)^{n+1}} がわかる。実用上はより弱い結果だがより評価のしやすいものを用いることもある。上記の式から簡単な評価をしてみると、任意の n に対して (n/3)n < n! であり、また n ≥ 6 のとき n! < (n/2)n であることなどが分かる。 大きな n に対して n ! をよりよく評価するにはスターリングの公式 n ! ∼ 2 π n ( n e ) n {\displaystyle n!\sim {\sqrt {2\pi n}}\left({\frac {n}{e}}\right)^{n}} を利用する。（ここで ∼ {\displaystyle \sim } は両辺の比が 1 に収束することを表す。）実は任意の n に対して 2 π n ( n e ) n < n ! < 2 π n ( n e ) n e 1 / 12 n {\displaystyle {\sqrt {2\pi n}}\left({\frac {n}{e}}\right)^{n}<n!<{\sqrt {2\pi n}}\left({\frac {n}{e}}\right)^{n}e^{1/12n}} であることが証明できる。 log(n !) の別な近似はシュリニヴァーサ・ラマヌジャンにより log n ! ≈ n log n − n + log [ n { 1 + 4 n ( 1 + 2 n ) } ] 6 + log π 2 {\displaystyle \log n!\approx n\log n-n+{\frac {\log \left[n\left\{1+4n\left(1+2n\right)\right\}\right]}{6}}+{\frac {\log \pi }{2}}} したがって n ! ∼ 2 π n ( n e ) n ( 1 + 1 2 n + 1 8 n 2 ) 1 / 6 {\displaystyle n!\sim {\sqrt {2\pi n}}\left({\frac {n}{e}}\right)^{n}\left(1+{\frac {1}{2n}}+{\frac {1}{8n^{2}}}\right)^{1/6}} と与えられている。この近似の誤差は、スターリングの公式よりも小さい。
※この「階乗の増大度」の解説は、「階乗」の解説の一部です。
「階乗の増大度」を含む「階乗」の記事については、「階乗」の概要を参照ください。
- 階乗の増大度のページへのリンク
