階乗
数学において非負整数 n の階乗(かいじょう、factorial)n ! は、1 から n までの全ての整数の積である。例えば、
6! = 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 720
である。空積の規約のもと 0!  1 と定義する。
階乗は数学の様々な場面に出現するが、特に組合せ論、代数学、解析学などが著しい。階乗の最も基本的な出自は n 個の相異なる対象を1列に並べる方法(対象の置換)の総数が n! 通りであるという事実である。
階乗の定義は、最も重要な性質を残したまま、非整数を引数とする函数に拡張することができる。そうすれば解析学における著しい手法などの進んだ数学を利用できるようになる。
いくつか同値な条件により定義することが可能である。
n!=\prod_{k=1}^n k=n\times\left(n-1\right)\times\cdots\times3\times2\times1
n! = \begin{cases}
1, & \text{if } n = 0 \\
n \times \left(n-1\right)!, & \text{if } n > 0
\end{cases}
微分に関する「冪の微分法則」を用いた定義
n! = \frac{d^n}{dx^n}x^n \quad\left(n\geq 0\right)
n! = ( n 元集合の置換の総数 )
上記の何れの定義においても、
0! = 1
となることが織り込み済みである(最初の定義では「 0 項の積は 1 と定める」という規約によって)空集合から空集合への全単射は空写像ただ1つ存在する。。このように定義することの理由は:
零個の対象の置換は(「何もしない」という)ちょうど一通りであること。
など様々に挙げることができる。
より進んだ数学においては、引数が非整数の場合にも階乗函数を定義することができる(後述)。そういった一般化された定義のもとでの階乗は関数電卓や、Maple や Mathematica などの数学ソフトウェアで利用できる。
多くのプログラミング言語において、再帰的な定義を利用し、プロシージャの再帰呼び出しを用いた階乗の実装が可能である。
以下はC言語での例である。例示するコードではunsigned long long型を使用しているが、unsigned long long型では小さな階乗(21!)でもオーバーフローしてしまうため、大きな階乗については任意精度演算による実装を検討すべきである。
階乗を含む公式は数学の多くの分野に現れるけれども、階乗のおおもとの出自は組合せ論にある。相異なる n 個の対象の順列(k-順列)の総数は n! 通りである。
階乗はしばしば「順番を無視する」という事実を反映するものとして分母に現れる。古典的な例としては n 個の元から k 個の元を選ぶ組合せ(k-組合せ)の総数が挙げられる。このような組合せは順列から得ることができる。実際、k-順列の総数
n^{\underline k}=n(n-1)(n-2)\cdots(n-k+1)
において、順番のみが違う(k-組合せでは違いが無視される)k-順列が k ! 通りずつ存在するから、k-組合せの総数は
\frac{n^{\underline k}{k!}=\frac{n(n-1)(n-2)\cdots(n-k+1)}{k(k-1)(k-2)\cdots1}
となる。この数は、二項冪 (1 + X)n における Xk の係数となることから、二項係数 \tbinom nk とも呼ばれる。
代数学に現れる階乗にはいくつも理由があるが、既述の如く二項展開の係数として現れたり、ある種の演算の対称化 において置換による平均化を行うなど、組合せ論的な理由で現れるものもある。
微分積分学においても階乗は例えばテイラー級数の分母として現れるが、これは冪函数 xn の n 階導函数が n ! であることを補正する定数である。確率論でも階乗は用いられる。
階乗は数式操作にも有効である。例えば n の k-順列の総数を
n^{\underline k}=\frac{n!}{(n-k)!}
と書けば、(この数値を計算することを考えれば効率が悪くなるが)二項係数の対称性
\binom nk=\frac{n^{\underline k}{k!}=\frac{n!}{(n-k)!k!}=\frac{n^{\underline{n-k}}{(n-k)!}=\binom n{n-k}
を見るには都合がよい。
階乗は数論にも多くの応用を持つ。特に n ! は n 以下の全ての素数で整除されねばならない。このことの帰結として、n ≥ 5 が合成数となる必要十分条件は
(n-1)!\equiv 0 \pmod n
が満たされることである。より強い結果としてウィルソンの定理は
(p-1)!\equiv -1 \pmod p
が p が素数であるための必要十分条件であることを述べる。
ルジャンドルの公式は n ! の素因数分解に現れる p の重複度が
\sum_{i=1}^{\infty} \left \lfloor \frac{n}{p^i} \right \rfloor
であることを示す。これは
\frac{n - s_p(n)}{p - 1}
と書いてもよい。ただし、sp(n) は n の p 進展開の係数の和である。
n ! が素数となる n は 2 のみである。n! ± 1 の形の素数は階乗素数と呼ばれる。
1! より大きな階乗は全て偶数である(これらは明らかに因数 2 を持ち、2 の倍数である)。同様に、5! より後の階乗は 10 の倍数(2 と 5 を因数に持つ)であり、十進展開の末尾の零。
ブロカールの問題とは、
n!+1 = m^2
を満たす n, m は存在するか、という問題である。2015年9月現在、これを満たす (n, m) の組このような (n, m) を、ブラウン数 (Brown numbers) と呼ぶ。は
(4, 5), (5, 11), (7, 71)
しか見つかっていない。ABC予想が真であれば、解は有限個しかないことが、Marius Overholt により示されている。
\sum_{n=0}^{\infty} \frac{1}{n!} = \frac{1}{1} + \frac{1}{1} + \frac{1}{2} + \frac{1}{6} + \frac{1}{24}  + \frac{1}{120} + \dotsb = e
を与える(ネイピア数を参照)。この和は無理数となるけれども、階乗に適当な正整数を掛けて和が有理数となるようにすることができる。例えば、
\sum_{n=0}^{\infty} \frac{1}{ \left(n+2 \right)n!} = \frac{1}{2}+\frac{1}{3}+\frac{1}{8}+\frac{1}{30}+\frac{1}{144}+\dotsb=1.
この級数の値が 1 となることを見るには、その部分和が 1 − 1/(n+2)! であることを確認すればよい。したがって、階乗数の全体は無理列を成さない。
n が増えるにつれて、階乗 n ! は n を変数とする任意の多項式函数あるいは指数函数よりも早く増加する(ただし、二重指数関数よりは遅い)。
n ! の近似式の多くは自然対数
\log n! = \sum_{x=1}^n \log x
であることを利用する。もっとも単純に得られる log(n!) の近似値を評価する式は、上記の式と以下の積分:
\int_1^n \log x \, dx \leq \sum_{x=1}^n \log x \leq \int_0^n \log (x+1) \, dx
によって与えられる。積分を評価すれば
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\left(\frac ne\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!\sim \sqrt{2\pi n}\left(\frac{n}{e}\right)^n
を利用する。(ここで \sim は両辺の比が 1 に収束することを表す。)実は任意の n に対して
\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! \approx n\log n - n + \frac {\log\left[n \left\{1+4n \left(1+2n \right) \right\} \right]} {6} + \frac {\log \pi} {2}
n! \sim \sqrt{2\pi n}\left(\frac{n}{e}\right)^n
\left( 1 + \frac{1}{2n} + \frac{1}{8n^2} \right)^{1/6}
と与えられている。この近似の誤差は、スターリングの公式よりも小さい。
負の整数を除けば、階乗関数は非整数の値に対しても定義することができるが、そのためには解析学の道具立てが必要である。そのように階乗の値を「補間」して得られるものの一つがガンマ函数 Γ(z) である(ただし引数が 1 だけずれる)。これは負の整数を除く任意の複素数 z に対して定義される。z の実部が正である場合には
\Gamma(z)=\int_0^\infty t^{z-1} e^{-t}\, dt
で与えられる。ガンマ函数と階乗との関係は、任意の自然数 n に対して
n!=\Gamma(n+1)
が成り立つことである。オイラーのもともとの定義式は
\Gamma(z)=\lim_{n\to\infty}\frac{n^zn!}{\displaystyle\prod_{k=0}^n (z+k)}
である。ガウスの導入した別表記として、負でない実数 z に対するパイ函数 Π(z) は
\Pi(z)=\int_0^\infty t^{z} e^{-t}\,dt
を満たす。ガンマ函数との関係は
\Pi(z) = \Gamma(z+1)
である。非負整数 n に対し
\Pi(n) = n!
が成り立つことを思えば、こちらのほうが階乗を補完した函数としては適していると言えるかもしれない。さてパイ函数は階乗が満たすのと同じ漸化式
\Pi(z) = z\Pi(z-1)
を、しかし定義される限り任意の複素数 z に対して満たす。事実としてはこれはもう漸化式ではなくて函数等式と見るべきものであるが。この函数等式をガンマ函数に関するものに書き換えれば
\Gamma(n+1)=n\Gamma(n)
となる。階乗を延長したものがパイ函数なのだから、定義可能な任意の複素数 z に対して
z! := \Pi(z)
と定めることは可能である。これらの補間函数を用いて半整数における階乗の値を定めるならば、例えば
\Gamma\left (\frac{1}{2}\right )=\left (-\frac{1}{2}\right )!=\Pi\left (-\frac{1}{2}\right ) = \sqrt{\pi}
が成り立ち、さらに自然数 n ∈ N に対して
\Gamma\left (\frac{1}{2}+n\right ) = \left (-\frac{1}{2}+n\right )! = \Pi\left (-\frac{1}{2}+n\right ) = \sqrt{\pi} \prod_{k=1}^n {2k - 1 \over 2} = {(2n)! \over 4^n n!} \sqrt{\pi} = {(2n-1)! \over 2^{2n-1}(n-1)!} \sqrt{\pi}
が得られる。例えば
\Gamma\left (4.5 \right ) = 3.5! = \Pi\left (3.5\right ) = {1\over 2}\cdot{3\over 2}\cdot{5\over 2}\cdot{7\over 2} \sqrt{\pi} = {8! \over 4^4 4!} \sqrt{\pi} = {7! \over 2^7 3!} \sqrt{\pi} = {105 \over 16} \sqrt{\pi} \approx 11.63.
同様に n ∈ N に対して
\Gamma\left (\frac{1}{2}-n\right ) = \left (-\frac{1}{2}-n\right )! = \Pi\left (-\frac{1}{2}-n\right ) = \sqrt{\pi} \prod_{k=1}^n {2 \over 1 - 2k} = {(-4)^n n! \over (2n)!} \sqrt{\pi}
が成り立ち、例えば
\Gamma\left (-2.5 \right ) = (-3.5)! = \Pi\left (-3.5\right ) = {2\over -1}\cdot{2\over -3}\cdot{2\over -5} \sqrt{\pi} = {(-4)^3 3! \over 6!} \sqrt{\pi} = -{8 \over 15} \sqrt{\pi} \approx -0.9453.
パイ函数が殆ど全ての複素数値に対して定義される階乗の延長として唯一のものでないことはもちろんである。それは定義域において解析的としても同じことである。しかし、ふつうはこれが階乗の複素函数への最も自然な延長であるものと考える。例えば、ボーア・モレルップの定理はガンマ函数が Γ(1)  1 かつ函数等式 Γ(n + 1)  nΓ(n) を満足する、ガウス平面の全域で有理型かつ実軸の正の部分で対数凸となるような唯一の函数であることを述べる。同様の主張はパイ函数に関しても、函数等式 Π(n)  nΠ(n − 1) に関して述べられる。
そうは言うものの、解析的函数論の意味で恐らくより簡明な、階乗の値を補間する複素函数は存在する。例えばアダマールの「ガンマ」函数はガンマ函数とは異なり整函数になる。
\begin{align}n! = \Pi(n) &= \prod_{k = 1}^\infty \left(\frac{k+1}{k}\right)^n\!\!\frac{k}{n+k} \\ &= \left[ \left(\frac{2}{1}\right)^n\frac{1}{n+1}\right]\left[ \left(\frac{3}{2}\right)^n\frac{2}{n+2}\right]\left[ \left(\frac{4}{3}\right)^n\frac{3}{n+3}\right]\cdots \end{align}
についても考察している。これは上記のガンマ函数に関する公式と同じものと見做すことができる。しかしこの公式は収束が遅く、実用的な意味でパイ函数やガンマ函数の値を計算することに利用することはできない。
複素変数の階乗の値をガンマ函数による表現を通して評価することができる。絶対値 ρ と偏角 φ を用いて
f=\rho \exp(i\varphi)=(x+iy)!=\Gamma(x+iy+1)
と書けば、絶対値一定曲線 ρ  (定数) と偏角一定曲線 φ  (定数) を等値線として格子を描くことができる。一定間隔で引いた等値線の間にさらに細かく等値線を引けば、それが補間で得られる値である。極である負の整数においては絶対値と偏角が定義できず、またその周辺で等値線は密になる。
!z! < 1 に対してはテイラー展開
z!=\sum_{n=0}^{\infty} g_n z^n
が利用できる。この展開のより多くの項は、Sageのような計算機代数システムで計算できる。
大きな値に対する階乗の値の近似をディガンマ函数の積分を通じて連分数表示を用いて記述できる。この方法はスティルチェスによるもので、z!  exp(P(z)) と書けば P(z) は
P(z) = p(z) + \log(2\pi)/2 - z + \left(z+\frac{1}{2}\right)\log(z)
で、スティルチェスはこの第一項 p(z) の連分数展開
p(z)=\cfrac{a_0}{z+
\cfrac{a_1}{z+
\cfrac{a_2}{z+
\cfrac{a_3}{z+\ddots}}
を与えた。
さて、任意の複素数 z ≠ 0 に対して log(z!)  P(z) あるいは log(Γ(z + 1))  P(z) とするのは誤りでありFebruary 2015、実際には実軸の近くの特定の範囲の z でしか成り立たない(一方 !ℑ(Γ(z + 1))! < π である。引数の実部は大きいほど、虚部はより小さくなければならない。しかし逆の関係式 z!  exp(P(z)) は原点を除くガウス平面の全域で有効である。ただし実軸の負の部分では収束性は弱くなるFebruary 2015(特異点の周辺ではどのような近似もよい収束性を得ることが難しい)。一方、!ℑ(z)! > 2 または ℜ(z) > 2 の範囲では上記の六つの係数は double 精度の複素数に対してその階乗の近似値を得るのに十分である。より高い精度でより多くの係数を計算するには rational QD-scheme (H. Rutishauser's QD algorithm)を用いる。
関係式 n!  n × (n − 1)! を使えばある整数に対する階乗をそれより「小さい」整数の階乗から計算できる。この関係式を逆に使えば、「大きい」整数に対して与えられた階乗から
(n-1)! = \frac{n!}{n}
と計算することも可能である。しかし注意すべきは、これでは負の整数に関する階乗を計算することはできないということである(この式に従って (−1)! を計算するには零除算が必要となりこれ以下の負の整数における階乗の値の計算は不可能となる)。このことはガンマ函数においても同じことで、ガンマ函数は負の整数を除くガウス平面の全域において定義できるにも拘らず、負の整数における値だけは定義することができない。
多重指数\alpha = (\alpha_1, \alpha_2,\ldots,\alpha_n)に対し階乗は、
\alpha ! = \alpha_1! \cdot \alpha_2! \cdots \alpha_n!
と定義できる。これは例えば、多変数関数の展開に使われる。
マンジュル・バルガヴァは階乗を一般のデデキント環上で定義し、いくつかの古典的な問題を解決するために用いた。それらの階乗は整数ではなく、イデアルとなる。
階乗の類似として、二重階乗 n!! は自然数 n に対し一つ飛ばしに積を取る。二重階乗 n!! は階乗 n! の二回反復合成 (n!)! とは異なる。
(2n)!!=(2n)(2n-2)\cdots(2)=2^n n!
(2n+1)!!=(2n+1)(2n-1)\cdots(1)=\frac{(2n+1)!}{(2n)!!}
奇数 n  1, 3, 5, 7, … に対する二重階乗の最初の方の値は
1, 3, 15, 105, 945, 10395, 135135, …, (A001147)
偶数 n  0, 2, 4, 6, 8, … に対する二重階乗の値の最初の方は
1, 2, 8, 48, 384, 3840, 46080, 645120, … (A000165)
で与えられる。
負の奇数にも拡張される( \left(-(2n+1) \right)!! = {(-1)^n} / {(2n-1)!!}
)。また、複素数値への拡張として、以下が知られている。
z!!={2}^{ \left[1+2z-\cos(\pi z) \right]/4}{\pi}^{ \left[\cos (\pi z)-1 \right]/4}\Gamma \left(1+\frac{1}{2} z\right)
より一般に多重階乗 (multifactorial) は、連続した整数の積である通常の階乗 n!、一つ飛ばしの積である二重階乗 n!!、二つ飛ばしの積である三重階乗 n!!! または n!3、三つ飛ばしの四重階乗 n!!!! または n!4 などを総称して言う。
三重階乗の例
1、4、28、280、3640。
2、10、80、880、12320。
3、18、162、1944、29160。
4、28、280、3640、58240。
5、40、440、6160、104720。
6、54、648、9720、174960。
7、70、910、14560、276640。
8、88、1232、20944、418880。
9、108、1620、29160、612360。
10、130、2080、39520、869440。
四重階乗の例
1、5、45、585。
2、12、120、1680。
3、21、231、3465。
4、32、384、6144。
5、45、585、9945。
6、60、840、15120。
7、77、1155、21945。
8、96、1536、30720。
9、117、1989、41769。
10、140、2520、55440。
一般の k-重階乗 n!k は正整数 n に関して帰納的に
n!_k= \begin{cases}
1 &\text{if }n=0,\\
n &\text{if }0<n<k,\\
n\, \left((n-k)!_k \right) &\text{if }n\ge k.
\end{cases}
と定義できる。これと異なる定義として
z!^{(k)} = z(z-k)\cdots (k+1)
= k^{(z-1)/k}\left(\frac{z}{k}\right)\left(\frac{z-k}{k}\right)\cdots \left(\frac{k+1}{k}\right)
= k^{(z-1)/k} \frac{\Gamma\left(\frac{z}{k}+1\right)}{\Gamma\left(\frac{1}{k}+1\right)}.
とするものもある。
自然数 n, k に対して、n の k-順列の総数 nk は n から始めて上から k 個の連続する整数の積を取る(ある意味で不完全な階乗とも呼べる)階乗の類似物であった。これを下降階乗冪と呼ぶ。その反対に n から始めて下から k 個の連続する整数の積をとったもの nk を上昇階乗冪といい、これら二つを総称して階乗冪と呼ぶ。ただし一般に自然数に限らず(実数や複素数などに値をとる)x を変数として
\begin{align}
x^{\underline{k} & =\prod_{i=0}^{k-1}(x-i),\\
x^{\overline{k} &=\prod_{i=0}^{k-1}(x+i)
\end{align}
を考えることが多い。明らかに自然数 n に対して
n^{\underline{k} = \frac{n!}{(n-k)!},\quad n^{\overline{k}=\frac{(n+k-1)!}{(n-1)!},
n!= n^{\underline{n} = 1^{\overline{n}.
また一般に実数 x ≠ 0 に対して
x^{\underline{0}=x^{\overline{0}=1
と定義する(空積も参照)が x  0 のときもそうであるかは規約による(例えば上記の関係式 n!  nn は n  0 のとき  1  0!  00 で矛盾しない。0^0も参照)。
素数階乗 (Primorial) n# は最初の n-個の素数の総乗
n\# = \prod_{i=1}^{n} p_i
である。A002110。
これは、素数が無限に存在するという命題の証明に用いられることがある。
の超階乗(superfactorial)は、階乗を入れ子に拡張したものである。ドル記号$を用いて書かれる。またLawrence Hollom氏が開発した超階乗配列表記は階乗をベースとした配列表記で従来の階乗や超階乗より遥かに大きな増加速度を持つ。
定義"sf"
n\$={}^{n!}n! = \underbrace{n!^{n!^{\scriptstyle n!^\textstyle\,\cdot}^\textstyle\,\cdot}^\textstyle\,\cdot\,}^{\scriptstyle n!}_{n!}
nが3以上になると、非常に大きい値になる。
これとは異なる種類の超階乗の定義がある。 The Encyclopedia of Integer Sequences は、超階乗(superfactorial)を定義した。例として、4の超階乗は次のようになる。
\mathrm{sf}(4)=1! \times 2! \times 3! \times 4!=288. \,
一般的にこの定義における超階乗は下の式で定義される。
定義"sf"
\mathrm{sf}(n)
=\prod_{k=1}^n k! =\prod_{k=1}^n k^{n-k+1}
=1^n\cdot2^{n-1}\cdot3^{n-2}\cdot4^{n-3}\cdots(n-1)^2\cdot n^1.
これは以下と同値:
\mathrm{sf}(n)
=\prod_{0 \le i < j \le n} (j-i).
最初のいくつかの値は、次のようになる:
超階乗は、複素数値にも拡張できる。その結果はバーンズのG関数と呼ばれる。定義は次のようになる。
G(z+1)=(2\pi)^{z/2} \text{exp}\left(- \frac{z+z^2(1+\gamma)}{2} \right) \, \prod_{k=1}^{\infty} \left\{ \left(1+\frac{z}{k}\right)^k \text{exp}\left(\frac{z^2}{2k}-z\right) \right\}
自然数に対しては、以下が成り立っている。
G(n+2)= \mathrm{sf}(n)=\begin{cases} 0&\text{if }n=-1,-2,\dots\\ \prod_{i=0}^{n} i!&\text{if }n=0,1,2,\dots\end{cases}
ハイパー階乗(hyperfactorial)は、以下で定義される。
H(n)= \prod_{k=1}^n k^k= 1^1\cdot2^2\cdot3^3\cdots(n-1)^{n-1}\cdot n^n
これはとても大きくなっていく。最初のいくつかの値はつぎの通りである。
1, 4, 108, 27648, 86400000, ……
ハイパー階乗は定義域を複素数にまで拡張できる。それはK函数と呼ばれ、以下で定義される。
K(z)=(2\pi)^{(-z+1)/2} \exp\left[\begin{pmatrix} z\\ 2\end{pmatrix}+\int_0^{z-1} \ln(t!)\,dt\right].
自然数nに対し、次が成り立つ。
K(n+1)=1^1\, 2^2\, 3^3\, 4^4\, \cdots n^n.