스털링 공식(Stirling's formula)

n개를 한 줄로 세우는 방법의 수(순열⁠, permutation⁠) $n! = 1 \cdot 2 \cdot 3 \cdots n$은 무섭게 빨리 자랍니다. 10!은 약 363만, 20!은 약 $2.4 \times 10^{18}$입니다. 스털링 공식은 이 곱을 제곱근과 거듭제곱만으로 어림합니다. $n =$ 으로 두면

두 수의 차이는 n이 커질수록 오히려 커지지만, 비율은 1로 극한⁠(limit)⁠을 가집니다. 이런 뜻의 "≈"(기호로 ∼)는 소수 정리⁠(prime number theorem)⁠가 쓰는 것과 같은 말입니다. 상대오차는 대략 $1/(12n)$이라 n = 10에서 이미 1%보다 작습니다.

곱을 합으로. 로그를 취하면 곱이 합이 됩니다: $\ln n! = \ln 2 + \ln 3 + \cdots + \ln n$. 폭이 1이고 높이가 $\ln k$인 막대들의 넓이⁠(area)⁠ 합, 곧 $\ln x$의 리만 합입니다. 그러니 곡선 아래 넓이인 정적분⁠(definite integral)⁠ $\int_1^n \ln x\,dx = n\ln n - n + 1$과 비슷하고, 양변에 지수함수⁠(exponential function)⁠를 씌우면 $n! \approx e\,(n/e)^n$이라는 뼈대가 벌써 잡힙니다.

막대는 곡선 위로 조금씩 삐져나옵니다. 삐져나온 조각은 거의 삼각형이고, 높이들을 모두 이어 붙이면 $\ln n$이 되므로 넓이 합은 대략 $\tfrac12 \ln n$입니다. 여기서 $\sqrt n$이 나옵니다. 남는 자잘한 오차들은 수렴⁠(convergence)⁠하는 급수⁠(series)⁠로 모여 상수가 됩니다. 지금 $\ln n! - \int_1^n \ln x\,dx =$ , 공식이 예측하는 $\tfrac12\ln n + \ln\sqrt{2\pi} - 1 =$ 입니다.

√(2π)는 어디서 오는가. 상수를 정확히 잡으려면 다른 길이 필요합니다. 부분적분을 n번 하면 $n! = \int_0^\infty x^n e^{-x}\,dx$입니다. 적분⁠(integral)⁠하는 함수⁠(function)⁠는 $x = n$에서 가장 높고, 그 근처에서 로그를 테일러 전개해 2차항까지 남기면 $x^n e^{-x} \approx n^n e^{-n}\, e^{-(x-n)^2/(2n)}$, 폭이 $\sqrt n$인 정규분포⁠(normal distribution)⁠의 종 모양입니다. 종 아래 넓이는 가우스 적분으로 $\sqrt{2\pi n}$이고, 이것을 곱하면 스털링 공식입니다. 이것이 증명이 되려면 종에서 멀리 떨어진 부분의 넓이와 2차항 뒤에 버린 항들의 영향이 n이 커질수록 무시할 만해진다는 것을 따로 보여야 하는데, 실제로 그렇습니다. 1730년 무렵 드무아브르가 같은 꼴의 근사를 얻었지만 상수는 수치로만 알았고, 그것이 $\sqrt{2\pi}$임을 밝힌 사람이 스코틀랜드의 수학자 제임스 스털링입니다(1730년 책 『차분법』).

이어지는 곳. 이항계수⁠(binomial coefficient)⁠ $\binom{2n}{n} = (2n)!/(n!)^2$에 공식을 넣으면 $4^n/\sqrt{\pi n}$이 되어, 동전을 2n번 던져 앞면이 정확히 절반일 확률⁠(probability)⁠이 $1/\sqrt{\pi n}$로 줄어듦을 알 수 있습니다. 앞면이 절반에서 조금 벗어난 k에 대해서도 같은 계산을 하면, 이항분포⁠(binomial distribution)⁠의 막대 높이가 종 모양 곡선 $e^{-x^2/2}$을 따른다는 드무아브르–라플라스 정리가 나옵니다. 이것이 중심극한정리⁠(central limit theorem)⁠의 첫 모습입니다. 합을 적분으로 어림하는 요령은 조화급수⁠(harmonic series)⁠가 $\ln n$처럼 자란다는 계산과 같은 것입니다. 카탈랑 수⁠(Catalan number)⁠ $\binom{2n}{n}/(n+1)$도 같은 방법으로 $4^n/(n^{3/2}\sqrt\pi)$처럼 자람을 압니다. 비교만 하는 정렬이 가려내야 할 순서는 n!가지이므로 적어도 $\log_2 n!$번 비교해야 하는데, 스털링 공식으로 이 값이 약 $n\log_2 n$임을 알 수 있습니다(비교 정렬의 하한⁠, comparison sorting lower bound⁠).