階乗


階乗
型	組合せ論
基本関数	乗算
急増加関数	$f_{2}(n)$

階乗はすべての自然数に対して適用される関数で、このように定義される^[1]^[2]。

$$n! = \prod^n_{i = 1} i = n \cdot (n - 1) \cdot \ldots \cdot 4 \cdot 3 \cdot 2 \cdot 1.$$

例えば $6! = 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 720$ である。$n$ 個の異なる物体を並べる方法は、 $n!$ 通りある。なぜならば、1つ目の物体を置く場所は $n$ 通りあり、２つ目の物体を置く場所は $n - 1$ 通りあり、と物体を1つ置く場所が1つずつ減っていき、それらをかけ合わせるためである。定義により、$0! = 1$ となる。ゼロ個の物体を並べる方法は1通りである。

$n!$ という記法が考案される前は、 $n$ という記法が一般的であった。

階乗は、 $0! = 1$ と $n! = n \cdot (n - 1)!$ から再帰的に定義できる。$n!$の最初のいくつかの値は、$n = 0, 1, 2, 3, 4, \ldots$ に対して 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800 である。

性質[]

階乗の逆数無限和は $\sum^{\infty}_{i = 0} i! = \frac{1}{0!} + \frac{1}{1!} + \frac{1}{2!} + \frac{1}{3!} + \cdots = 2.71828182845904\ldots$で、数学定数$e$として知られる。実際、$e^x = 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \cdots$で、重要な性質$\frac{d}{dx}e^x = e^x$を証明するのに使える。

$n! = \Gamma (n + 1)$ ($\Gamma (x)$はガンマ関数)より、 $n! = \int^{\infty}_0 e^{-t} \cdot t^{n + 1} dt$である。このことより、すべての正の実数と非整数の負の実数に対し定義できる:

$\left(\frac{1}{2}\right)! = \frac{\sqrt{\pi}}{2}$
$\left(-\frac{1}{2}\right)! = \sqrt{\pi}$

10進法では、各桁の階乗の和が元の数に等しい数は、自明なものを除いて二つしかない: $145 = 1! + 4! + 5!$ and $40585 = 4! + 0! + 5! + 8! + 5!$.

$n!$の10進表記での最後につく0の個数は$\sum_{k = 1} \lfloor n / 5^k\rfloor$で与えられる。^[3]例えば、10000!は2000 + 400 + 80 + 16 + 3 = 2499のゼロがある。一般的に、$b$進法での$n$!のゼロの個数は$\sum_{k = 1} \lfloor n / p^k\rfloor$である。$p$は$b$の最大の素因数である。

特別な数[]

100の階乗は次に与えられる:

93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

指数表記では、9.3326215443 × 10¹⁵⁷に等しい。グーゴル^3/2程である。

Lawrence Hollomは200!をファクズルと呼んでいる。

1000の階乗は4.0238726007 × 10²⁵⁶⁷程である。

増加速度の評価[]

階乗$n!$は指数関数$n^n$と同程度の増加速度をもつ。スターリングの近似式より$\log n! \sim n\log n-n$と近似できることから^[4]、最も大きな寄与をする$n\log n$の項だけ取り出して$n! \sim e^{n\log n} = n^n$である。

変種[]

Aalbert Torsiusは階乗の変種を考え出した。$x!n = \prod^{x}_{i = 1} i!(n - 1) = 1!(n - 1) \cdot 2!(n - 1) \cdot \ldots \cdot x!(n - 1)$、$x!0 = x$。^[5]

$x!n$は「xのレベルnの階乗」と呼ぶ。$x!1$は普通の階乗であり、$x!2$はSimonとPlouffeの超階乗 $x\$$である。

特別な場合の$x!x$はトリアンという関数として知られる。

その他、階乗のq-類似体としてQ階乗がある。

疑似コード[]

// Standard factorial function
function factorial(z):
    result := 1
    for i from 1 to z:
        result := result * i
    return result

// Generalized factorial, using Lanczos approximation for gamma function

g := 7
coeffs := [0.99999999999980993, 676.5203681218851, -1259.1392167224028, 771.32342877765313, -176.61502916214059, 12.507343278686905, -0.13857109526572012, 9.9843695780195716e-6, 1.5056327351493116e-7]

function factorialReal(z):
    ag := coeffs[0]
    for i from 1 to g + 1:
        ag := ag + coeffs[i] / (z + i)
    zg := z + g + 0.5
    return sqrt(2 * pi) * zg^{z + 0.5} * e^-zg * ag

// Torsius' factorial extension
function factorialTorsius(z, x):
    if x = 0:
        return z
    if x = 1:
        return factorial(z)
    result := 1
    for i from 1 to z:
        result := result * factorialTorsius(i, x - 1)
    return result

出典[]

[1] Factorial from Wolfram MathWorld

[2] Factorials from PurpleMath

[3] Factorials and Trailing Zeroes from PurpleMath

[4] Stirling's Approximation from Wolfram MathWorld

[5] [1]

[1]

[2]

[3]

[4]

[5]