階乗

階乗​${\displaystyle 0}$は${\displaystyle 1}$または記号で表すと、${\displaystyle 0!=1}$この定義にはいくつかの理由がある。

• のために${\displaystyle n=0}$定義​${\displaystyle n!}$積は、全く数の積を含まないため、空積（因数のない積）が乗法単位元に等しいというより広い慣習の一例である。^{[ 22 ]}
• ゼロ個のオブジェクトの順列はちょうど1つだけ存在する。順列するものが何もない場合、唯一の再配置は何もしないことである。^{[ 21 ]}
• この慣例により、組み合わせ論における多くの恒等式が、そのパラメータのすべての有効な選択に対して有効になります。たとえば、すべての選択方法の数${\displaystyle n}$要素のセットから${\displaystyle n}$は${\textstyle {\tbinom {n}{n}}={\tfrac {n!}{n!0!}}=1,}$二項係数の恒等式は、${\displaystyle 0!=1}$[ ^{23 ]​}
• と${\displaystyle 0!=1}$階乗の漸化式は、${\displaystyle n=1}$したがって、この慣例により、階乗の再帰的計算では、基本ケースとしてゼロの値のみが必要となり、計算が簡略化され、追加の特殊ケースが不要になります。^{[ 24 ]}
• 設定${\displaystyle 0!=1}$指数関数など、多くの公式をべき級数として簡潔に表現することを可能にする。${\textstyle e^{x}=\sum _{n=0}^{\infty }{\frac {x^{n}}{n!}}.}$^{[ 14 ]}
• この選択はガンマ関数に一致する。${\displaystyle 0!=\ガンマ (0+1)=1}$ガンマ関数は、この値で別途選択を必要としない複素数の連続関数として定義されます。^{[ 25 ]}

関数として${\displaystyle n}$階乗は指数関数よりも速い成長を示すが、二重指数関数よりは遅い成長を示す。^{[ 48 ]}その成長率は${\displaystyle n^{n}}$しかし、指数関数的に遅くなる。この結果に近づく一つの方法は、階乗の自然対数を取ることで、積の公式を和に変換し、その和を積分によって推定することである。 $${\displaystyle \ln n!=\sum _{x=1}^{n}\ln x\approx \int _{1}^{n}\ln x\,dx=n\ln n-n+1.}$$ 結果を指数化し（そして無視できるほどの${\displaystyle +1}$項) 近似値${\displaystyle n!}$として${\displaystyle (n/e)^{n}}$^{[ 49 ]}台形公式 を用いて積分によって上下の和をより慎重に制限すると、この推定値にはに比例する補正係数が必要であることがわかる。${\displaystyle {\sqrt {n}}}$この補正の比例定数は、ウォリス積から求めることができ、それは次のように表される。${\displaystyle \pi }$階乗と2のべき乗の極限比として。これらの補正の結果はスターリングの近似式です: ^{[ 50 ]}$${\displaystyle n!\sim {\sqrt {2\pi n}}\left({\frac {n}{e}}\right)^{n}\,.}$$ ここでは、${\displaystyle \sim }$シンボルは、${\displaystyle n}$が無限大に近づくと、左右の比率は${\displaystyle 1}$極限では、スターリングの公式は漸近級数の最初の項を与え、項数を増やすとさらに正確になります。^{[ 51 ]}$${\displaystyle 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}}}-{\frac {571}{2488320n^{4}}}+\cdots \right).}$$別のバージョン（オイラー・マクローリンの公式 から直接導出された近似式）は、補正項に奇数指数のみを必要とするため、より速く収束します。^{[ 51 ]}$${\displaystyle n!\sim {\sqrt {2\pi n}}\left({\frac {n}{e}}\right)^{n}\exp \left({\frac {1}{12n}}-{\frac {1}{360n^{3}}}+{\frac {1}{1260n^{5}}}-{\frac {1}{1680n^{7}}}+\cdots \right).}$$これらの公式の他の多くのバリエーションも、シュリニヴァーサ・ラマヌジャン、ビル・ゴスパー、その他 によって開発されている。 ^{[ 51 ]}

比較ソートの分析に使用される階乗の二進対数は、スターリングの近似式を使用して非常に正確に推定できます。以下の式では、${\displaystyle O(1)}$この項はビッグオー記法を呼び出します。^{[ 45 ]}$${\displaystyle \log _{2}n!=n\log _{2}nn\log _{2}e+{\frac {1}{2}}\log _{2}n+O(1).}$$

階乗の積の公式は、${\displaystyle n!}$は、最大で の素数で割り切れる。${\displaystyle n}$、そしてそれより大きい素数では割り切れない。^{[ 52 ]}割り切れるかどうかについてのより正確な情報は、各素数の指数を与えるルジャンドルの公式によって与えられる。${\displaystyle p}$素因数分解において${\displaystyle n!}$[ ^{53 ] [ 54 ]​}$$\displaystyle \sum _{i=1}^{\infty }\left\lfloor {\frac {n}{p^{i}}}\right\rfloor ={\frac {n-s_{p}(n)}{p-1}}.}$$ ここ$s_p(n)$は底の合計を表します-${\displaystyle p}$桁​${\displaystyle n}$この式で与えられる指数は、より技術的には階乗のp進評価と呼ばれる。^{[ 54 ]}二項係数の積の公式にルジャンドルの公式を適用すると、二項係数の因数分解における各素数の指数に関する同様の結果であるクンマーの定理が得られる。 ^{[ 55 ]}階乗の素因数をさまざまな方法で素数のべき乗にグループ化すると、階乗の乗法分割が得られる。^{[ 56 ]}

ルジャンドルの公式の特殊なケース${\displaystyle p=5}$階乗の十進数表現における末尾のゼロの数を示します。 ^{[ 57 ]}この式によれば、ゼロの数は、5 進数の桁を減算することによって得られます。${\displaystyle n}$から${\displaystyle n}$、そして結果を4で割る。^{[ 58 ]}ルジャンドルの公式は、素数の指数が${\displaystyle p=2}$は常に指数よりも大きい${\displaystyle p=5}$5 の各因数は 2 の因数とペアにすることで、これらの末尾のゼロのいずれかを生成できます。[ ^{57 ]階乗}の先頭の桁はベンフォードの法則に従って分布します。^{[ 59 ]}任意の基数におけるすべての桁列は、その基数における何らかの階乗数の最初の桁列です。^{[ 60 ]}

階乗の可除性に関するもう一つの結果であるウィルソンの定理は、次のように述べている。${\displaystyle (n-1)!+1}$は割り切れる${\displaystyle n}$かつその場合に限り${\displaystyle n}$は素数である。^{[ 52 ]}任意の整数に対して${\displaystyle x}$ケンプナー関数​​${\displaystyle x}$最小値で与えられる${\displaystyle n}$そのために${\displaystyle x}$分ける${\displaystyle n!}$^{[ 61 ]}ほぼすべての数（漸近密度がゼロの例外のサブセットを除くすべて）について、それは最大の素因数と一致する。${\displaystyle x}$[ ^{62 ]​}

2つの階乗の積、${\displaystyle m!\cdot n!}$常に均等に分割します${\displaystyle (m+n)!}$^{[ 63 ]}他の階乗の積に等しい階乗は無限に存在する。${\displaystyle n}$が階乗の任意の積である場合、${\displaystyle n!}$同じ積にさらに1つの階乗を掛けたものに等しい。${\displaystyle (n-1)!}$他の階乗の積であるが、この「自明な」形式ではない階乗の既知の例は次のとおりです。${\displaystyle 9!=7!\cdot 3!\cdot 3!\cdot 2!}$、${\displaystyle 10!=7!\cdot 6!=7!\cdot 5!\cdot 3!}$、そして${\displaystyle 16!=14!\cdot 5!\cdot 2!}$[ ^{64 ]} abc予想から、非自明な例^は有限個しかないことがわかる。 ^{[ 65 ]}

次数 の原始多項式の値の最大公約数${\displaystyle d}$整数を割り切る${\displaystyle d!}$[ ^{63 ]​}

階乗を連続関数に拡張する方法は無数に存在する。^{[ 66 ]}これらの方法の中で最も広く用いられているのは^{[ 67 ]} 、ガンマ関数を用いる方法である。ガンマ関数は、正の実数に対して積分として定義できる。$${\displaystyle \Gamma (z)=\int _{0}^{\infty }x^{z-1}e^{-x}\,dx.}$$ 結果として得られる関数は、非負整数の階乗に関連している。${\displaystyle n}$方程式により $${\displaystyle n!=\ガンマ (n+1),}$$ これは、非整数引数の階乗の定義として使用できます。すべての値において${\displaystyle x}$両方${\displaystyle \Gamma (x)}$そして$\displaystyle \Gamma (x-1)$が定義されると、ガンマ関数は関数方程式に従う。$${\displaystyle \ガンマ (n)=(n-1)\ガンマ (n-1),}$$階乗の漸化式 を一般化する。 ^{[ 66 ]}

同じ積分は、より一般的には任意の複素数に対して収束する。${\displaystyle z}$実部が正である。オイラーの反射公式を解くことで、複素平面の残りの非整数点にも拡張できる。$${\displaystyle \Gamma (z)\Gamma (1-z)={\frac {\pi }{\sin \pi z}}.}$$ しかし、この式は整数には使えません。なぜなら、整数では、${\displaystyle \sin \pi z}$項はゼロ除算を引き起こします。この拡張プロセスの結果は解析関数（より具体的には有理型関数）であり、ガンマ関数の積分公式の解析接続です。これは、単純極を持つ非正の整数を除いて、すべての複素数でゼロ以外の値を持ちます。同様に、これは負の整数以外のすべての複素数での階乗の定義を提供します。^{[ 67 ]} ガンマ関数を他の連続的な階乗補間と区別するガンマ関数の特性の1つは、ガンマ関数（1だけオフセット）が、階乗を補間し、同じ関数方程式に従う正の実数上の唯一の対数凸関数であることを示すボーア・モレラップの定理によって与えられます。ヘルムート・ヴィーラントの関連する一意性定理によれば、複素ガンマ関数とそのスカラー倍は、正の複素半平面上で関数方程式を満たし、実部が 1 から 2 の間の複素数に対して有界である唯一の正則関数である。^{[ 68 ]}

階乗値を補間する他の複素関数には、非正の整数を含むすべての複素数上の整関数であるアダマールのガンマ関数があります。 ^{[ 69 ] [ 70 ]} p進数では、大きな整数の階乗 ( p進整数の密な部分集合) はルジャンドルの公式に従ってゼロに収束するため、その値に近い連続関数はどこでもゼロになってしまいます。代わりに、p進ガンマ関数は、階乗のpで割り切れる因子を省略した修正された形式の階乗の連続補間を提供します。^{[ 71 ]}

ディガンマ関数はガンマ関数の対数微分です。ガンマ関数が階乗の連続補間を1だけずらして提供するのと同様に、ディガンマ関数は調和数の連続補間をオイラー・マスケローニ定数だけずらして提供します。^{[ 72 ]}

階乗関数は、科学計算機によく見られる機能です。^{[ 73 ]}また、 Python の数学関数モジュール^{[ 74 ]}やBoost C++ ライブラリ^{[ 75 ]}などの科学プログラミングライブラリにも含まれています。

効率が問題にならない場合、階乗の計算は簡単です。初期化された変数に、次の値を順次掛けるだけです。${\displaystyle 1}$までの整数によって${\displaystyle n}$この計算の単純さから、さまざまなコンピュータプログラミングスタイルや手法の使用において一般的な例となっている。^{[ 76 ]}${\displaystyle n!}$反復^{[ 77 ]}を用いた擬似コードでは次のように表現できる。

define factorial( n ): f := 1 for i := 1, 2, 3, ..., n : f := f * i return f

または、その再帰関係に基づく再帰^{[ 78 ]を使用する}

factorial( n ) を定義します。もしn = 0ならば1 を返します。n * factorial( n − 1)を返します。

その計算に適した他の方法としては、メモ化^{[ 79 ]} 、動的計画法^{[ 80 ]}、関数型計画法^{[ 81 ]}などがある。これらのアルゴリズムの計算複雑性は、各算術演算が一定時間かかり、各数値が一定量の記憶領域を使用する単位コストランダムアクセスマシンモデルを使用して分析できる。このモデルでは、これらの方法は、${\displaystyle n!}$時間が経つにつれて${\displaystyle O(n)}$、反復バージョンはスペースを使用します${\displaystyle O(1)}$末尾再帰用に最適化されていない限り、再帰バージョンは呼び出しスタックを格納するために線形スペースを必要とします。^{[ 82 ]}ただし、この計算モデルは、次の場合にのみ適しています。${\displaystyle n}$十分に小さいので${\displaystyle n!}$マシンワードに収まるように。^{[ 83 ]} 12! と 20! は、それぞれ32 ビット^{[ 84 ]}と64 ビット整数に格納できる最大の階乗です。^{[ 85 ]}浮動小数点数はより大きな階乗を表現できますが、正確ではなく近似的に表現され、12! より大きい階乗ではオーバーフローします。${\displaystyle 170!}$[ ^{84 ]​}

より大きな階乗の正確な計算には、急速な増加と整数オーバーフローのため、任意精度演算が関係します。計算時間は、結果の桁数またはビット数の関数として分析できます。^{[ 85 ]}スターリングの公式によれば、${\displaystyle n!}$もっている${\displaystyle b=O(n\log n)}$ビット。^{[ 86 ]}シェーンハーゲ・シュトラッセンアルゴリズムは、${\displaystyle b}$-ビット積の時間${\displaystyle O(b\log b\log \log b)}$乗算アルゴリズムの高速化により、${\displaystyle O(b\log b)}$は既知である。^{[ 87 ]}しかし、階乗の計算には単一の乗算ではなく繰り返し積が含まれるため、これらの時間制限は直接適用されない。この設定では、計算は${\displaystyle n!}$1から${\displaystyle n}$順番に行うのは非効率的です。なぜなら、${\displaystyle n}$乗算のうち一定の割合が時間を要する${\displaystyle O(n\log ^{2}n)}$それぞれ合計時間${\displaystyle O(n^{2}\log ^{2}n)}$より良いアプローチは、一連の数を乗算する分割統治アルゴリズムとして乗算を実行することです。${\displaystyle i}$数字を2つの部分列に分割することによって${\displaystyle i/2}$数値を乗算し、各部分列を乗算し、最後に1回の乗算で結果を組み合わせます。この階乗の計算方法は合計で${\displaystyle O(n\log ^{3}n)}$: 1 つの対数は階乗のビット数から、2 つ目は乗算アルゴリズムから、3 つ目は分割統治法から得られます。^{[ 88 ]}

さらに効率が良いのは、 n ! を素因数分解から計算する方法で、これは指数を積に展開するよりも二乗による指数計算の方が速いという原理に基づいています。 ^{[ 86 ] [ 89 ]}アーノルド・シェーンハーゲによるこのアルゴリズムは、まずまでの素数のリストを見つけることから始まります。${\displaystyle n}$例えばエラトステネスの篩を用いて、各素数の指数を計算するためにルジャンドルの公式を使用します。次に、以下の再帰アルゴリズムを使用して、これらの指数で素数のべき乗の積を計算します。

• 分割統治法を用いて、指数が奇数の素数の積を計算する。
• すべての指数を2で割り（小数点以下を切り捨てて整数にする）、これらのより小さい指数で素数のべき乗の積を再帰的に計算し、結果を2乗する。
• 前の2つのステップの結果を掛け合わせる

までのすべての素数の積${\displaystyle n}$は${\displaystyle O(n)}$-ビット数、素数定理により、最初のステップにかかる時間は${\displaystyle O(n\log ^{2}n)}$一方の対数は分割統治法から、もう一方の対数は乗算アルゴリズムから得られます。アルゴリズムの再帰呼び出しでは、素数定理を再び利用して、対応する積のビット数が再帰の各レベルで一定の係数で減少することを証明できます。したがって、すべての再帰レベルでのこれらのステップの合計時間は等比数列で加算され、${\displaystyle O(n\log ^{2}n)}$2番目のステップでの二乗と3番目のステップでの乗算にかかる時間は再び${\displaystyle O(n\log ^{2}n)}$なぜなら、それぞれは、ある数とある数の単一の乗算だからです。${\displaystyle O(n\log n)}$ビット。繰り返しますが、再帰の各レベルで、関係する数値は一定の割合のビットを持ちます（そうでないと、繰り返し二乗すると最終結果が大きくなりすぎるため）。したがって、再帰呼び出しのこれらのステップにかかる時間は、等比数列で加算されます。${\displaystyle O(n\log ^{2}n)}$結果として、アルゴリズム全体には時間がかかります${\displaystyle O(n\log ^{2}n)}$結果のビット数が同じ単一の乗算に比例する。^{[ 89 ]}