Stirling's approximation (or
Stirling's formula) is an approximation for large
factorials. It is named in honour of
James Stirling. Formally, it states:
- <math>\lim_{n \rightarrow \infty} {n!\over \sqrt{2 \pi n} \; \left(\frac{n}{e}\right)^{n} } = 1</math>
which is often written as
- <math>n! \sim \sqrt{2 \pi n} \; \left(\frac{n}{e}\right)^{n}</math>
(See
limit,
square root,
π,
e.) For large
n, the right hand side is a good approximation for
n!, and much faster and easier to calculate. For example, the formula gives for 30! the approximation 2.6451 × 10
32 while the correct value is about 2.6525 × 10
32.
It can be shown that
- <math>n^n \ge n! \ge \left(\frac{n}{2}\right)^\frac{n}{2}</math>
using Stirling's appoximation.
The speed of convergence of the above limit is expressed by the formula
- <math>n! = \sqrt{2 \pi n} \; \left(\frac{n}{e}\right)^{n}\left(1 + \Theta\left(\frac{1}{n}\right)\right)</math>
where Θ(1/
n) denotes a function whose asymptotical behavior for
n→∞ is like a constant times 1/
n; see
Big O notation.
More precisely still:
- <math>n! = \sqrt{2 \pi n} \; \left(\frac{n}{e}\right)^{n}e^{\lambda_n}</math>
with
- <math>\frac{1}{12n+1} < \lambda_n < \frac{1}{12n}</math>
The formula, together with precise estimates of its error, can be derived as follows. Instead of approximating n!, one considers the natural logarithm ln(n!) = ln(1) + ln(2) + ... + ln(n); the Euler-Maclaurin formula gives estimates for sums like these. The goal, then, is to show the approximation formula in its logarithmic form:
- <math>\ln n! \approx \left(n+\frac{1}{2}\right)\ln n - n +\ln\left(\sqrt{2\pi}\right)</math>
The formula was first discovered by Abraham de Moivre in the form
- <math>n!\sim [{\rm constant}]\cdot n^{n+1/2} e^{-n}</math>
Stirling's contribution consisted of showing that the "constant"
is <math>\sqrt{2\pi}</math>.