階乗

数学において、で表される非負整数の階乗は、以下のすべての正の整数の積です。の階乗は、 とその次に小さい階乗 の積にも等しくなります。 たとえば、 0! の値は、空の積 の慣例に従って 1 です。^[1] ${\displaystyle n}$${\displaystyle n!}$${\displaystyle n}$${\displaystyle n}$${\displaystyle n}$$${\displaystyle {\begin{aligned}n!&=n\times (n-1)\times (n-2)\times (n-3)\times \cdots \times 3\times 2\times 1\\&=n\times (n-1)!\\\end{aligned}}}$$$${\displaystyle 5!=5\times 4!=5\times 4\times 3\times 2\times 1=120.}$$

階乗は、インドの数学ではジャイナ教の正典、ユダヤ教の神秘家によるタルムードの書物『セフェル・イェツィラー』など、いくつかの古代文化で発見されています。階乗演算は数学の多くの分野で見られますが、特に組合せ論では、異なるオブジェクトの可能な異なるシーケンス、つまり順列を数えるのが最も基本的な用途で、次が存在します。数学的解析では、階乗は指数関数やその他の関数のべき級数で使用され、代数、数論、確率論、およびコンピューターサイエンスにも応用されています。 ${\displaystyle n}$${\displaystyle n!}$

階乗関数の数学の多くは、18 世紀後半から 19 世紀初頭にかけて発展し始めました。 スターリングの近似は、大きな数の階乗の正確な近似値を提供し、指数関数的増加よりも速く増加することを示しています。ルジャンドルの公式は、階乗の素因数分解における素数の指数を記述し、階乗の末尾のゼロを数えるために使用できます。ダニエル ベルヌーイとレオンハルト オイラーは、階乗関数を、負の整数を除いて 複素数の連続関数、つまり (オフセット)ガンマ関数に補間しました。

階乗と密接に関係する他の多くの注目すべき関数と数列には、二項係数、二重階乗、下降階乗、原始数、部分階乗が含まれます。階乗関数の実装は、さまざまなコンピュータ プログラミングスタイルの例としてよく使用され、科学計算用電卓や科学計算ソフトウェア ライブラリに含まれています。積の公式や漸化式を使用して大きな階乗を直接計算するのは効率的ではありませんが、同じ桁数の数値の高速乗算アルゴリズムの時間と定数倍以内に一致する、より高速なアルゴリズムが知られています。

階乗の概念は多くの文化で独立して発生しました。

• インド数学において、階乗に関する最も古い記述の一つは、ジャイナ教の文献の正典の一つであるアヌヨーガドヴァーラ・スートラ^[2]に見られるもので、紀元前300年から紀元後400年まで様々な年代が付けられている。^[3]この経典では、一組の項目の並び替えられた逆順を他の（「混合」）順序から分離し、階乗の通常の積の式から2を引くことで混合順序の数を評価する。順列の積の規則は、紀元後6世紀のジャイナ教の僧侶ジナバドラによっても記述されている。^[2]ヒンドゥー教の学者たちは、少なくとも1150年以降、階乗の公式を使ってきました。その年、バースカラ2世は著書『リーラーヴァティー』の中で、ヴィシュヌが4つの特徴的な物体（ほら貝、円盤、棍棒、蓮の花）を4つの手に持つ方法が何通りあるかという問題、および10本の手を持つ神に関する同様の問題に関連して階乗について言及しました。^[4]
• 中東の数学では、タルムード時代（西暦200年から500年）のヘブライ神秘創造書『セフェル・イェツィラー』に、ヘブライ語アルファベットから形成できる単語の数の調査の一環として、7!までの階乗が記載されている。^{[5] [6]}階乗は、8世紀のアラブ人文法学者アル＝ハリール・イブン・アフマド・アル＝ファラヒディも同様の理由で研究した。^[5]アラブの数学者イブン・アル＝ハイサム（別名アルハゼン、965年頃-1040年頃）は、階乗と素数を結び付けるウィルソンの定理を初めて定式化した。^[7]
• ヨーロッパでは、ギリシャの数学に多少の組合せ論が含まれていて、プラトンが理想的なコミュニティの人口として5,040（階乗）を使ったのは有名だが、これは部分的には割り切れる性質のためである^{[8] 。しかし、古代ギリシャで階乗が研究されていたという直接的な証拠はない。代わりに、ヨーロッパで階乗について最初に取り組んだのは、ユダヤ人学者の}シャベタイ・ドンノロによるもので、セフェル・イェツィラーの一節を解説した。^[9] 1677年、イギリスの作家ファビアン・ステッドマンは、階乗をチェンジ・リンギング（調律された鐘を複数鳴らす音楽芸術）に応用したことを説明した。^{[10] [11]}

15世紀後半以降、階乗は西洋の数学者による研究対象となった。1494年の論文で、イタリアの数学者ルカ・パチョーリは食卓の配置の問題に関連して、11!までの階乗を計算した。^[12] クリストファー・クラビウスは1603年にヨハネス・デ・サクロボスコの著作に関する注釈で階乗について論じ、1640年代にはフランスの博学者マリン・メルセンヌがクラビウスの著作に基づいて、64!までの大規模な（しかし完全に正確ではない）階乗表を出版した。^[13]階乗の逆数を係数とする指数関数のべき級数は、1676年にアイザック・ニュートンがゴットフリート・ヴィルヘルム・ライプニッツに宛てた手紙の中で初めて定式化された。^[14]初期ヨーロッパ数学における階乗に関するその他の重要な研究としては、1685年にジョン・ウォリスが書いた論文での広範な記述、1721年にアブラハム・ド・モアブルが書いたの大きな値に対する階乗の近似値の研究、1729年にジェームズ・スターリングがド・モアブルに書いた、スターリングの近似として知られるようになったことを述べた手紙、およびダニエル・ベルヌーイとレオンハルト・オイラーが同時期に書いた、階乗関数のガンマ関数への連続拡張を定式化した研究などがある。^[15]アドリアン・マリー・ルジャンドルは、階乗を素因数分解する際の指数を記述するルジャンドルの公式を、1808年の数論のテキストに含めた。^[16]${\displaystyle n}$

階乗の表記法は、1808年にフランスの数学者クリスチャン・クランプによって導入された。^[17]他にも多くの表記法が使われてきた。階乗の引数をボックスの左辺と下辺で半分囲むという、後の別の表記法は、イギリスとアメリカでしばらく人気があったが、おそらくは印刷が難しいため使われなくなった。^{[17] 「階乗」（元々フランス語：} factorielle ）という言葉は、1800年にルイ・フランソワ・アントワーヌ・アルボガストによって^[18]、ファア・ディ・ブルーノの公式に関する最初の著作の中で初めて使用されたが、^[19]等差数列の積というより一般的な概念を指していた。この名前が指す「因数」は、階乗の積の公式の項である。^[20]${\displaystyle n!}$${\displaystyle \vert \!{\underline {\,n}}}$

正の整数の階乗関数は、^[1]以下のすべての正の整数の積によって定義されます。これは、積表記法 でより簡潔に書くと、^[1]となります。${\displaystyle n}$${\displaystyle n}$ $${\displaystyle n!=1\cdot 2\cdot 3\cdots (n-2)\cdot (n-1)\cdot n.}$$ $${\displaystyle n!=\prod _{i=1}^{n}i.}$$

この積の公式を最後の項以外すべてを残すように変更すると、より小さな階乗に対して同じ形式の積が定義される。これは再帰関係につながり、それによれば階乗関数の各値は前の値に${\displaystyle n}$ を掛けることで得られる: ^[21] たとえば、。$${\displaystyle n!=n\cdot (n-1)!.}$$${\displaystyle 5!=5\cdot 4!=5\cdot 24=120}$

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

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

階乗関数の最も初期の用途は、順列を数えることです。異なるオブジェクトを順序付けるには、さまざまな方法があります。 ^{[26]階乗は、オブジェクトのさまざまな順序を説明するために、}組合せ論の多くの式でより広く使用されます。たとえば、二項係数は、要素を含むセットから要素の組み合わせ（要素のサブセット）を数え、式を使用して階乗から計算できます。 ^[27]第一種スターリング数は階乗の合計になり、同じ数のサイクルを持つサブセットにグループ化されたの順列を数えます。[ ^{28]組合せ論のもう1つの用途は、}入れ替わり、つまりどの要素も元の位置のままにならない入れ替わりの数を数えることです。アイテムの入れ替わりの数は に最も近い整数です。^[29]${\displaystyle n!}$${\displaystyle n}$ ${\displaystyle {\tbinom {n}{k}}}$${\displaystyle k}$ ${\displaystyle k}$${\displaystyle n}$ $${\displaystyle {\binom {n}{k}}={\frac {n!}{k!(nk)!}}.}$$${\displaystyle n}$${\displaystyle n}$ ${\displaystyle n!/e}$

代数学では、階乗は二項定理から生じ、二項定理では二項係数を使用して和のべき乗を展開します。^{[30]また、}ニュートンの対称多項式に対する恒等式など、特定の多項式の族を互いに関連付けるために使用される係数にも現れます。^{[31]順列を}数える際の階乗の使用は、代数的に言い換えることもできます。つまり、階乗は有限対称群の順序です。^[32]微積分学では、階乗はファディブルーノの高次導関数の連鎖公式に現れます。^[19]数学的解析では、階乗はべき級数の分母に頻繁に現れ、最も顕著なのは指数関数の級数です。^[14] また、他のテイラー級数（特に三角関数と双曲関数のテイラー級数）の係数にも現れ、の番目の導関数から生じるの因数をキャンセルします。^[33]べき級数における階乗のこの用法は、指数生成関数を介して解析的組合せ論につながり、指数生成関数は、大きさの要素を持つ組合せクラスに対してべき級数として定義される^[34] $${\displaystyle e^{x}=1+{\frac {x}{1}}+{\frac {x^{2}}{2}}+{\frac {x^{3}}{6}}+\cdots =\sum _{i=0}^{\infty }{\frac {x^{i}}{i!}},}$$${\displaystyle n!}$${\displaystyle n}$ ${\displaystyle x^{n}}$${\displaystyle n_{i}}$${\displaystyle i}$ $${\displaystyle \sum _{i=0}^{\infty}{\frac {x^{i}n_{i}}{i!}}.}$$

数論において、階乗の最も顕著な性質は までのすべての正の整数で が割り切れることであり、素因数についてはルジャンドルの公式によってより正確に記述される。従って、任意の大きな素数は数 の素因数として見つけることができ 、素数の数は無限であるというユークリッドの定理の証明につながる。 ^{[35] が}それ自体素数であるとき、それは階乗素数と呼ばれる。^[36]関連して、やはりシュリニヴァーサ・ラマヌジャンによって提起されたブロカールの問題 は、形式 の平方数の存在に関する。 [37]対照的に、数はすべて合成数でなければならないため、任意に大きな素数ギャップの存在が証明される。^{[38]ポール}・エルデシュの最初の結果の 1 つである、形式の任意の区間に素数が存在するというベルトランの公理の初等的証明は、階乗の割り切れる性質に基づいていた。^{[39] [40]}階乗数法は、各桁の位の値が階乗である数値の混合基数表記法である。 ^[41]${\displaystyle n!}$${\displaystyle n}$${\displaystyle n!\pm 1}$${\displaystyle n!\pm 1}$${\displaystyle n!+1}$${\displaystyle n!+2,n!+3,\dots n!+n}$${\displaystyle [n,2n]}$

階乗は確率論で広く使われており、例えばポアソン分布^[42]やランダム順列の確率[ ^43]などで用いられている。コンピュータサイエンスでは、順列の総当たり探索の解析に現れるほかに^[44] 、項目の集合を比較ソートするために必要な比較回数の下限値^[45]や、セルあたりのキーの分布をポアソン分布で正確に近似できる連鎖ハッシュテーブルの解析でも階乗が現れる。 ^{[46]さらに、階乗は}量子物理学や統計物理学の式にも自然に現れ、そこでは粒子の集合のすべての可能な順列を考えることが多い。統計力学では、ボルツマンのエントロピー式やザッカー・テトロード方程式などのエントロピーの計算で、ギブスのパラドックスを避けるために、ミクロ状態のカウントを区別できない各タイプの粒子の数の階乗で割って補正しなければならない。量子物理学は、なぜこれらの補正が必要なのかという根本的な理由を示しています。^[47]${\displaystyle \log _{2}n!=n\log _{2}nO(n)}$${\displaystyle n}$

の${\displaystyle n}$関数として、階乗は指数関数的増加よりも速く増加しますが、二重指数関数よりも遅く増加します。^{[48]その増加率}は と${\displaystyle n^{n}}$似ていますが、指数係数だけ遅くなります。この結果に近づく方法の 1 つは、階乗の自然対数を取ってその積の式を合計に変換し、積分によって合計を推定することです。 結果を累乗すると（無視できる項は無視して）、は と近似します。^[49]台形則 を 使って積分によって上と下の両方の合計をより慎重に制限すると、この推定にはに比例する補正係数が必要であることがわかります。この補正の比例定数は、階乗と 2 の累乗の極限比として表されるWallis 積から見つけることができます。これらの補正の結果がスターリングの近似である：^[50] ここで、記号は、が無限大に近づくにつれて、左辺と右辺の比が極限で1に近づくことを意味している。スターリングの公式は漸近級数の最初の項を提供し、項の数が増えるほど精度が増す：^[51] 別のバージョンでは、補正項に奇数指数のみを使用する：^{[51]これらの公式のさまざまなバリエーションも、}シュリニヴァーサ・ラマヌジャン、ビル・ゴスパー、その他 によって開発されている。 ^[51]$${\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}}$${\displaystyle {\sqrt {n}}}$${\displaystyle \pi}$ $${\displaystyle n!\sim {\sqrt {2\pi n}}\left({\frac {n}{e}}\right)^{n}\,.}$$${\displaystyle \sim}$${\displaystyle n}$ $${\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).}$$ $${\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).}$$

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

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

に対するルジャンドルの公式の特殊なケースは、階乗の十進表現における末尾のゼロの数を与える。 ^[57]この公式によれば、ゼロの数は、 の底 5 の桁を から減算し、その結果を 4 で割ることで得られる。^[58]ルジャンドルの公式は、 の指数が の指数よりも常に大きいことを意味しており、したがって、5 の因数と 2 の因数を組み合わせると、これらの末尾のゼロの 1 つが生成されます。^[57]階乗の先頭の桁は、ベンフォードの法則に従って分布します。^[59]任意の底における数字のシーケンスはすべて、その底の階乗数の最初の桁のシーケンスです。^[60]${\displaystyle p=5}$${\displaystyle n}$${\displaystyle n}$${\displaystyle p=2}$${\displaystyle p=5}$

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

2 つの階乗の積 は、常にを割り切れる。^[63]他の階乗の積に等しい階乗は無限に存在する。 が階乗の積である場合、 は同じ積にさらに 1 つの階乗 を掛けたものに等しい。他の階乗の積でありながらこの「自明な」形式ではない階乗の例は、、、 のみである。^[64] abc予想から、自明でない例は有限個しかないことがわかる。^[65]${\displaystyle m!\cdot n!}$${\displaystyle (m+n)!}$${\displaystyle n}$${\displaystyle n!}$${\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!}$

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

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

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

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

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

階乗関数は科学計算用電卓の一般的な機能です。^[73]また、Python数学関数モジュール^[74]やBoost C++ライブラリ^[75]などの科学プログラミングライブラリにも含まれています。効率を気にしないのであれば、階乗の計算は簡単です。 に初期化された変数に${\displaystyle 1}$まで${\displaystyle n}$の整数を順に掛けるだけです。この計算の単純さから、さまざまなコンピュータプログラミングスタイルや方法を使用する際の一般的な例となっています。^[76]

の計算は反復法^[77]を用いた擬似コードで次のように 表現できる。${\displaystyle n!}$

階乗( n )を定義する:
   f  := 1i  := 1, 2, 3, ..., n
  の場合:
     f  := f * i はf
  を返します

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

階乗( n )を定義します:
  ( n = 0)の場合は1を返すn * 階乗( n − 1)

  を返す

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

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

指数を積に展開するよりも、 2乗による累乗の方が速いという原理に基づき、n ! を素因数分解から計算すると、さらに効率が良くなります。 ^{[86] [89]} Arnold Schönhageによるこのアルゴリズムは、まず までの素数のリストを探し、たとえばエラトステネスのふるいを使用して、ルジャンドルの公式を使用して各素数の指数を計算します。次に、再帰アルゴリズムを使用して、これらの指数で素数の累乗の積を計算します。 ${\displaystyle n}$

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

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

他にも階乗に似ているか階乗に関連する整数列がいくつかあります。

交代階乗

交代階乗は、最初の階乗の交代和の絶対値である。これらは主に素数性に関連して研究されてきた。素数になるものは有限個しかないが、この形式の素数の完全なリストは知られていない。^[90]${\displaystyle n}$${\textstyle \sum _{i=1}^{n}(-1)^{n-i}i!}$

バーガヴァ階乗

バーガヴァ階乗は、マンジュル・バーガヴァによって定義された整数列の族であり、階乗と同様の数論的性質を持ち、階乗自体も特別なケースとして含まれる。^[63]

二重階乗

ある奇数の正の整数${\displaystyle n}$までの全ての奇数の積はの二重階 乗と呼ばれ、と表記される。^[91]つまり、例えば、9!! = 1 × 3 × 5 × 7 × 9 = 945である。二重階乗は三角積分、^[92]半整数におけるガンマ関数の式や超球面の体積、^[93]二分木や完全マッチングの数え上げで用いられる。^{[91] [94]}${\displaystyle n}$${\displaystyle n!!}$$${\displaystyle (2k-1)!!=\prod _{i=1}^{k}(2i-1)={\frac {(2k)!}{2^{k}k!}}.}$$

指数階乗

三角数がからまでの数を足し合わせ、階乗がそれらの積をとるのと同じように、指数階乗は指数になります。指数階乗は と再帰的に定義されます。たとえば、4 の指数階乗は です。これらの数は、通常の階乗よりもはるかに速く増加します。^[95]${\displaystyle 1}$ ${\displaystyle n}$${\displaystyle a_{0}=1,\ a_{n}=n^{a_{n-1}}}$$${\displaystyle 4^{3^{2^{1}}}=262144.}$$

下降階乗

またはという表記は、まで数え上げ、 を含む整数の積が に等しいことを表すために使用されることがあります。これは、下降階乗または後退階乗としても知られ、表記はポッホハマー記号です。^[96]下降階乗は、項目の集合から抽出できる異なる項目の異なるシーケンスの数を数えます。^{[97]これらは、多項式の}高次導関数の係数として、^[98]およびランダム変数の階乗モーメントに使用されます。^[99]${\displaystyle (x)_{n}}$${\displaystyle x^{\underline {n}}}$${\displaystyle n}$${\displaystyle x}$${\displaystyle x!/(x-n)!}$${\displaystyle (x)_{n}}$${\displaystyle n}$${\displaystyle x}$

ハイパーファクタリアル

の超階乗は積である。これらの数はエルミート多項式の判別式を形成する。^{[100]これらは}K関数によって連続的に補間することができ、^[101]スターリングの公式^{[102]やウィルソンの定理[103]}と同様の式に従う。${\displaystyle n}$${\displaystyle 1^{1}\cdot 2^{2}\cdots n^{n}}$

ジョルダン・ポリア数

ジョーダン・ポリア数は階乗の積であり、繰り返しが許される。すべての木には対称性の数がジョーダン・ポリア数である対称群があり、すべてのジョーダン・ポリア数は何らかの木の対称性を数える。^[104]

原始的

原始数 は以下の素数の積である。この構成により、 は階乗に似た割り切れる性質を持つが、^[36]階乗とは異なり平方根を持たない。^[105]階乗素数と同様に、研究者は原始素数を研究してきた。^[36]${\displaystyle n\#}$${\displaystyle n}$ ${\displaystyle n!\pm 1}$ ${\displaystyle n\#\pm 1}$

サブファクタリアル

サブファクタリは、オブジェクトの集合の乱れの数を表します。サブファクタリは と表記されることもあり、 に最も近い整数に等しくなります。^[29]${\displaystyle n}$${\displaystyle !n}$${\displaystyle n!/e}$

スーパーファクタリアル

の超階乗は最初の階乗の積である。超階乗はバーンズG関数によって連続的に補間される。^[106]${\displaystyle n}$${\displaystyle n}$