In mathematics, Stirling's approximation (or Stirling's formula) is an asymptotic approximation for factorials. It is a good approximation, leading to accurate results even for small values of n {\displaystyle n} . It is named after James Stirling, though a related but less precise result was first stated by Abraham de Moivre. One way of stating the approximation involves the logarithm of the factorial:
ln n ! = n ln n − n + O ( ln n ) , {\displaystyle \ln n!=n\ln n-n+O(\ln n),}
where the big O notation means that, for all sufficiently large values of n {\displaystyle n} , the difference between ln n ! {\displaystyle \ln n!} and n ln n − n {\displaystyle n\ln n-n} will be at most proportional to the logarithm of n {\displaystyle n} . In computer science applications such as the worst-case lower bound for comparison sorting, it is convenient to instead use the binary logarithm, giving the equivalent form
log 2 n ! = n log 2 n − n log 2 e + O ( log 2 n ) . {\displaystyle \log _{2}n!=n\log _{2}n-n\log _{2}e+O(\log _{2}n).} The error term in either base can be expressed more precisely as 1 2 log ( 2 π n ) + O ( 1 n ) {\displaystyle {\tfrac {1}{2}}\log(2\pi n)+O({\tfrac {1}{n}})} , corresponding to an approximate formula for the factorial itself,
n ! ∼ 2 π n ( n e ) n . {\displaystyle n!\sim {\sqrt {2\pi n}}\left({\frac {n}{e}}\right)^{n}.}
Here the sign ∼ {\displaystyle \sim } means that the two quantities are asymptotic, that is, their ratio tends to 1 as n {\displaystyle n} tends to infinity.
History The formula was first discovered by Abraham de Moivre in 1721 in the form
n ! ∼ [ c o n s t a n t ] ⋅ n n + 1 2 e − n . {\displaystyle n!\sim [{\rm {constant}}]\cdot n^{n+{\frac {1}{2}}}e^{-n}.}
De Moivre gave an approximate rational-number expression for the natural logarithm of the constant. Stirling's contribution in 1730 consisted of showing that the constant is precisely 2 π {\displaystyle {\sqrt {2\pi }}} .
Derivation The simplest version of Stirling's formula is
n ! = 2 π n ( n e ) n ( 1 + O ( 1 n ) ) . {\displaystyle n!={\sqrt {2\pi n}}\left({\frac {n}{e}}\right)^{n}\left(1+O\!\left({\frac {1}{n}}\right)\right).}
It can be quickly obtained by approximating the sum
ln n ! = ∑ j = 1 n ln j {\displaystyle \ln n!=\sum _{j=1}^{n}\ln j}
with an integral:
∑ j = 1 n ln j ≈ ∫ 1 n ln x d x = n ln n − n + 1. {\displaystyle \sum _{j=1}^{n}\ln j\approx \int _{1}^{n}\ln x\,{\rm {d}}x=n\ln n-n+1.}
The full formula, together with precise estimates of its error, can be derived as follows. Instead of approximating n ! {\displaystyle n!} , one considers its natural logarithm, as this is a slowly varying function:
ln n ! = ln 1 + ln 2 + ⋯ + ln n . {\displaystyle \ln n!=\ln 1+\ln 2+\cdots +\ln n.}
The right-hand side of this equation minus
1 2 ( ln 1 + ln n ) = 1 2 ln n {\displaystyle {\tfrac {1}{2}}(\ln 1+\ln n)={\tfrac {1}{2}}\ln n}
is the approximation by the trapezoid rule of the integral
ln n ! − 1 2 ln n ≈ ∫ 1 n ln x d x = n ln n − n + 1 , {\displaystyle \ln n!-{\tfrac {1}{2}}\ln n\approx \int _{1}^{n}\ln x\,{\rm {d}}x=n\ln n-n+1,}
and the error in this approximation is given by the Euler–Maclaurin formula:
ln n ! − 1 2 ln n = ln 1 + ln 2 + ln 3 + ⋯ + ln ( n − 1 ) + 1 2 ln n = n ln n − n + 1 + ∑ k = 2 m ( − 1 ) k B k k ( k − 1 ) ( 1 n k − 1 − 1 ) + R m , n , {\displaystyle {\begin{aligned}\ln n!-{\tfrac {1}{2}}\ln n&=\ln 1+\ln 2+\ln 3+\cdots +\ln(n-1)+{\tfrac {1}{2}}\ln n\\&=n\ln n-n+1+\sum _{k=2}^{m}{\frac {(-1)^{k}B_{k}}{k(k-1)}}\left({\frac {1}{n^{k-1}}}-1\right)+R_{m,n},\end{aligned}}}
where B k {\displaystyle B_{k}} is a Bernoulli number, and Rm,n is the remainder term in the Euler–Maclaurin formula. Take limits to find that
lim n → ∞ ( ln n ! − n ln n + n − 1 2 ln n ) = 1 − ∑ k = 2 m ( − 1 ) k B k k ( k − 1 ) + lim n → ∞ R m , n . {\displaystyle \lim _{n\to \infty }\left(\ln n!-n\ln n+n-{\tfrac {1}{2}}\ln n\right)=1-\sum _{k=2}^{m}{\frac {(-1)^{k}B_{k}}{k(k-1)}}+\lim _{n\to \infty }R_{m,n}.}
Denote this limit as y {\displaystyle y} . Because the remainder Rm,n in the Euler–Maclaurin formula satisfies
R m , n = lim n → ∞ R m , n + O ( 1 n m ) , {\displaystyle R_{m,n}=\lim _{n\to \infty }R_{m,n}+O\!\left({\frac {1}{n^{m}}}\right),}
where big-O notation is used, combining the equations above yields the approximation formula in its logarithmic form:
ln n ! = n ln ( n e ) + 1 2 ln n + y + ∑ k = 2 m ( − 1 ) k B k k ( k − 1 ) n k − 1 + O ( 1 n m ) . {\displaystyle \ln n!=n\ln \left({\frac {n}{e}}\right)+{\tfrac {1}{2}}\ln n+y+\sum _{k=2}^{m}{\frac {(-1)^{k}B_{k}}{k(k-1)n^{k-1}}}+O\!\left({\frac {1}{n^{m}}}\right).}
Taking the exponential of both sides and choosing any positive integer m {\displaystyle m} , one obtains a formula involving an unknown quantity e y {\displaystyle e^{y}} . For m = 1, the formula is
n ! = e y n ( n e ) n ( 1 + O ( 1 n ) ) . {\displaystyle n!=e^{y}{\sqrt {n}}\left({\frac {n}{e}}\right)^{n}\left(1+O\!\left({\frac {1}{n}}\right)\right).}
The quantity e y {\displaystyle e^{y}} can be found by taking the limit on both sides as n {\displaystyle n} tends to infinity and using Wallis' product, which shows that e y = 2 π {\displaystyle e^{y}={\sqrt {2\pi }}} . Therefore, one obtains Stirling's formula.
Alternative derivations An alternative formula for n ! {\displaystyle n!} using the gamma function is
n ! = ∫ 0 ∞ x n e − x d x . {\displaystyle n!=\int _{0}^{\infty }x^{n}e^{-x}\,{\rm {d}}x.}
(as can be seen by repeated integration by parts). Rewriting and changing variables x = ny, one obtains
n ! = ∫ 0 ∞ e n ln x − x d x = e n ln n n ∫ 0 ∞ e n ( ln y − y ) d y . {\displaystyle n!=\int _{0}^{\infty }e^{n\ln x-x}\,{\rm {d}}x=e^{n\ln n}n\int _{0}^{\infty }e^{n(\ln y-y)}\,{\rm {d}}y.}
Applying Laplace's method one has
∫ 0 ∞ e n ( ln y − y ) d y ∼ 2 π n e − n , {\displaystyle \int _{0}^{\infty }e^{n(\ln y-y)}\,{\rm {d}}y\sim {\sqrt {\frac {2\pi }{n}}}e^{-n},}
which recovers Stirling's formula:
n ! ∼ e n ln n n 2 π n e − n = 2 π n ( n e ) n . {\displaystyle n!\sim e^{n\ln n}n{\sqrt {\frac {2\pi }{n}}}e^{-n}={\sqrt {2\pi n}}\left({\frac {n}{e}}\right)^{n}.}
Higher orders Further corrections can also be obtained using Laplace's method. Stirling's formula to two orders is
n ! = 2 π n ( n e ) n ( 1 + 1 12 n + O ( 1 n 2 ) ) . {\displaystyle n!={\sqrt {2\pi n}}\left({\frac {n}{e}}\right)^{n}\left(1+{\frac {1}{12n}}+O\!\left({\frac {1}{n^{2}}}\right)\right).}
From previous result, we know that Γ ( x ) ∼ x x e − x {\displaystyle \Gamma (x)\sim x^{x}e^{-x}} , so we "peel off" this dominant term, then perform two changes of variables, to obtain:
x − x e x Γ ( x ) = ∫ R e x ( 1 + t − e t ) d t {\displaystyle x^{-x}e^{x}\Gamma (x)=\int _{\mathbb {R} }e^{x\left(1+t-e^{t}\right)}\,dt}
To verify this:
∫ R e x ( 1 + t − e t ) d t = t ↦ ln t e x ∫ 0 ∞ t x − 1 e − x t d t = t ↦ t x x − x e x ∫ 0 ∞ e − t t x − 1 d t = x − x e x Γ ( x ) . {\displaystyle \int _{\mathbb {R} }e^{x\left(1+t-e^{t}\right)}\,dt\ {\overset {t\mapsto \ln t}{=}}\ e^{x}\int _{0}^{\infty }t^{x-1}e^{-xt}\,dt\ {\overset {t\mapsto {\frac {t}{x}}}{=}}\ x^{-x}e^{x}\int _{0}^{\infty }e^{-t}t^{x-1}\,dt=x^{-x}e^{x}\Gamma (x).}
Now the function t ↦ 1 + t − e t {\displaystyle t\mapsto 1+t-e^{t}} is unimodal, with maximum value zero. Locally around zero, it looks like − t 2 2 {\textstyle -{\frac {t^{2}}{2}}} , which is why we are able to perform Laplace's method. In order to extend Laplace's method to higher orders, we perform another change of variables by 1 + t − e t = − τ 2 2 {\textstyle 1+t-e^{t}=-{\frac {\tau ^{2}}{2}}} . This equation cannot be solved in closed form, but it can be solved by serial expansion, which gives us
t = τ − τ 2 6 + τ 3 36 + a 4 τ 4 + O ( τ 5 ) . {\displaystyle t=\tau -{\frac {\tau ^{2}}{6}}+{\frac {\tau ^{3}}{36}}+a_{4}\tau ^{4}+O\left(\tau ^{5}\right).}
Now plug back to the equation to obtain
x − x e x Γ ( x ) = ∫ R e − x τ 2 2 ( 1 − τ 3 + τ 2 12 + 4 a 4 τ 3 + O ( τ 4 ) ) d τ = 2 π ( x − 1 2 + x − 3 2 12 ) + O ( x − 5 2 ) . {\displaystyle {\begin{aligned}x^{-x}e^{x}\Gamma (x)&=\int _{\mathbb {R} }e^{-{\frac {x\tau ^{2}}{2}}}\left(1-{\frac {\tau }{3}}+{\frac {\tau ^{2}}{12}}+4a_{4}\tau ^{3}+O\left(\tau ^{4}\right)\right)\,d\tau \\&={\sqrt {2\pi }}\left(x^{-{\frac {1}{2}}}+{\frac {x^{-{\frac {3}{2}}}}{12}}\right)+O\left(x^{-{\frac {5}{2}}}\right).\end{aligned}}}
Notice how it is not actually necessary to find a 4 {\displaystyle a_{4}} , since it is cancelled out by the integral. Higher orders can be achieved by computing more terms in t = τ + ⋯ {\displaystyle t=\tau +\cdots } , which can be obtained programmatically.
Complex-analytic version A complex-analysis version of this method is to consider 1 n ! {\textstyle {\frac {1}{n!}}} as a Taylor coefficient of the exponential function
e z = ∑ n = 0 ∞ z n n ! , {\displaystyle e^{z}=\sum _{n=0}^{\infty }{\frac {z^{n}}{n!}},}
computed by Cauchy's integral formula as
1 n ! = 1 2 π i ∮ | z | = r e z z n + 1 d z . {\displaystyle {\frac {1}{n!}}={\frac {1}{2\pi i}}\oint \limits _{|z|=r}{\frac {e^{z}}{z^{n+1}}}\,dz.}
This line integral can then be approximated using the saddle-point method with an appropriate choice of contour radius r = r n {\displaystyle r=r_{n}} . The dominant portion of the integral near the saddle point is then approximated by a real integral and Laplace's method, while the remaining portion of the integral can be bounded above to give an error term.
Using the Central Limit Theorem and the Poisson distribution An alternative version uses the fact that the Poisson distribution converges to a normal distribution by the Central Limit Theorem. Since the Poisson distribution with parameter μ {\displaystyle \mu } converges to a normal distribution with mean μ {\displaystyle \mu } and variance μ {\displaystyle \mu } , their density functions will be approximately the same:
exp ( − μ ) μ x x ! ≈ 1 2 π μ exp ( − 1 2 ( x − μ μ ) 2 ) {\displaystyle {\frac {\exp(-\mu )\mu ^{x}}{x!}}\approx {\frac {1}{\sqrt {2\pi \mu }}}\exp \left(-{\frac {1}{2}}\left({\frac {x-\mu }{\sqrt {\mu }}}\right)^{2}\right)}
Evaluating this expression at the mean, at which the approximation is particularly accurate, simplifies this expression to:
exp ( − μ ) μ μ μ ! ≈ 1 2 π μ {\displaystyle {\frac {\exp(-\mu )\mu ^{\mu }}{\mu !}}\approx {\frac {1}{\sqrt {2\pi \mu }}}}
Taking logs then results in
− μ + μ ln μ − ln μ ! ≈ − 1 2 ln ( 2 π μ ) {\displaystyle -\mu +\mu \ln \mu -\ln \mu !\approx -{\frac {1}{2}}\ln(2\pi \mu )}
which can easily be rearranged to give:
ln μ ! ≈ μ ln μ − μ + 1 2 ln ( 2 π μ ) {\displaystyle \ln \mu !\approx \mu \ln \mu -\mu +{\frac {1}{2}}\ln(2\pi \mu )}
Evaluating at μ = n {\displaystyle \mu =n} gives the usual, more precise form of Stirling's approximation.
Speed of convergence and error estimates
Stirling's formula is in fact the first approximation to the following series (now called the Stirling series):
n ! ∼ 2 π n ( n e ) n ( 1 + 1 12 n + 1 288 n 2 − 139 51840 n 3 − 571 2488320 n 4 + 163879 209018880 n 5 − ⋯ ) . {\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}}}+{\frac {163879}{209018880n^{5}}}-\cdots \right).}
An explicit formula for the coefficients in this series was given by G. Nemes. Further terms are listed in the On-Line Encyclopedia of Integer Sequences as A001163 and A001164. The first graph in this section shows the relative error vs. n {\displaystyle n} , for 1 through all 5 terms listed above. The coefficients have the following asymptotic formula:
A 2 j + 1 ∼ ( − 1 ) j 2 ( 2 j )