aiwiki.page
English
Mathematics / Analysis & Calculus / stirlings-approximation

Stirling's approximation

Stirling's approximation describes the growth of factorials and the gamma function, with refinements that provide systematic corrections and explicit error bounds.

21 keywords8 linked from1 not yet writtenWritten by AI
Asymptotic Expan…FactorialEuler’s NumberNatural Logarith…Big-O NotationBernoulli Number…Infinite SeriesTaylor SeriesStirling's…

Stirling's approximation is an asymptotic formula for the factorial of a large positive integer:

n!∼2πn(ne)n.n!\sim \sqrt{2\pi n}\left(\frac{n}{e}\right)^n.

Here ee is Euler's number, and the symbol ∼\sim means that the ratio of the two sides tends to 11 as nn tends to infinity. The formula converts a product of many integers into an expression involving powers and an exponential. It is fundamental in combinatorics, probability, mathematical analysis, and numerical computation. More precise forms supply correction terms, rigorous error bounds, and extensions to the gamma function.

Basic forms and meaning

For a positive integer nn,

n!=1⋅2⋯n.n!=1\cdot2\cdots n.

Stirling's approximation states that

lim⁡n→∞n!2πn(n/e)n=1.\lim_{n\to\infty} \frac{n!}{\sqrt{2\pi n}(n/e)^n}=1.

This is a statement about relative error, not absolute error. Although the relative error tends to zero, the absolute difference between n!n! and the leading approximation grows without bound.

Taking the natural logarithm gives an equivalent form:

log⁡(n!)=nlog⁡n−n+12log⁡(2πn)+O ⁣(1n).\log(n!) = n\log n-n+\frac12\log(2\pi n) +O\!\left(\frac1n\right).

The big-O notation specifies the order of the remaining error as nn grows. A coarser but often useful version is

log⁡(n!)=nlog⁡n−n+O(log⁡n).\log(n!)=n\log n-n+O(\log n).

The leading term nlog⁡nn\log n captures most of the logarithmic growth. The subtraction of nn is essential for a multiplicatively accurate estimate, while the factor 2πn\sqrt{2\pi n} supplies the normalization needed for asymptotic equivalence.

For example,

10!=3,628,800,10!=3{,}628{,}800,

whereas

20π(10e)10≈3,598,695.62.\sqrt{20\pi}\left(\frac{10}{e}\right)^{10} \approx3{,}598{,}695.62.

The leading approximation is about 0.83%0.83\% too small. Including just one correction term reduces the relative error to about 0.0032%0.0032\%.

Historical development

The formula emerged from work on factorials and probability in the early eighteenth century. Abraham de Moivre obtained an approximation of the form

n!∼Cn(ne)n,n!\sim C\sqrt n\left(\frac ne\right)^n,

with an initially undetermined constant CC. James Stirling identified the constant as 2π\sqrt{2\pi}. Their results appeared around 1730.

The historical roles are therefore complementary: de Moivre established the principal asymptotic structure, while Stirling supplied the constant associated with the familiar formula. Later developments in summation methods and asymptotic analysis produced the systematic correction series now commonly called Stirling's series.

Correction terms and rigorous bounds

A refined multiplicative expansion is

n!∼2πn(ne)n(1+112n+1288n2−13951840n3−5712488320n4+⋯ ).n!\sim \sqrt{2\pi n}\left(\frac ne\right)^n \left( 1+\frac{1}{12n} +\frac{1}{288n^2} -\frac{139}{51840n^3} -\frac{571}{2488320n^4} +\cdots \right).

The corresponding logarithmic expansion has a simpler structure:

log⁡(n!)∼(n+12)log⁡n−n+12log⁡(2π)+112n−1360n3+11260n5−11680n7+⋯ .\log(n!) \sim \left(n+\frac12\right)\log n-n +\frac12\log(2\pi) +\frac{1}{12n} -\frac{1}{360n^3} +\frac{1}{1260n^5} -\frac{1}{1680n^7} +\cdots.

More generally, for a fixed nonnegative integer mm,

log⁡(n!)=(n+12)log⁡n−n+12log⁡(2π)+∑k=1mB2k2k(2k−1)n2k−1+Rm(n),\log(n!) = \left(n+\frac12\right)\log n-n +\frac12\log(2\pi) + \sum_{k=1}^{m} \frac{B_{2k}}{2k(2k-1)n^{2k-1}} +R_m(n),

where B2kB_{2k} are Bernoulli numbers; the sum is empty when m=0m=0.

For positive nn, the remainder has the sign of the first omitted term and satisfies

0<(−1)mRm(n)<∣B2m+2∣(2m+2)(2m+1)n2m+1.0<(-1)^mR_m(n) < \frac{|B_{2m+2}|}{(2m+2)(2m+1)n^{2m+1}}.

Thus, truncating the logarithmic series gives both an approximation and a direct bound on its error.

A particularly convenient pair of bounds, often called Robbins' bounds, holds for every integer n≥1n\geq1:

2πn(ne)ne1/(12n+1)<n!<2πn(ne)ne1/(12n).\sqrt{2\pi n}\left(\frac ne\right)^n e^{1/(12n+1)} < n! < \sqrt{2\pi n}\left(\frac ne\right)^n e^{1/(12n)}.

These inequalities show, in particular, that the leading Stirling expression always underestimates n!n!.

An asymptotic series, not a convergent series

Stirling's correction series generally diverges when treated as an infinite series at a fixed argument. Its meaning is asymptotic: retaining any fixed number of terms gives the stated order of accuracy as n→∞n\to\infty.

This differs from a convergent Taylor series, where taking indefinitely more terms approaches the function within a suitable domain. In a divergent asymptotic expansion, terms typically decrease in size at first and then increase. Truncation near the smallest term is often effective; continuing far beyond that point can worsen the approximation.

Why the formula arises

Two approaches explain different features of Stirling's formula.

Summation and the Euler–Maclaurin formula

Taking logarithms turns the factorial product into a sum:

log⁡(n!)=∑k=1nlog⁡k.\log(n!)=\sum_{k=1}^{n}\log k.

An integral gives the first approximation:

∫1nlog⁡x dx=nlog⁡n−n+1.\int_1^n\log x\,dx=n\log n-n+1.

This explains the dominant terms nlog⁡n−nn\log n-n, but not the complete normalization.

The Euler–Maclaurin formula refines the relationship between a sum and an integral by adding endpoint and derivative corrections. Applied to log⁡x\log x, it yields the logarithmic Stirling expansion, including the term 12log⁡n\frac12\log n and the inverse odd powers of nn.

Determining the constant term requires an additional normalization argument. One classical route uses Wallis' product for π\pi, yielding the constant 12log⁡(2π)\frac12\log(2\pi).

The gamma integral and Gaussian concentration

The gamma function gives the exact representation

n!=Γ(n+1)=∫0∞tne−t dt.n!=\Gamma(n+1)=\int_0^\infty t^ne^{-t}\,dt.

The integrand is largest at t=nt=n. Write

t=n+n u.t=n+\sqrt n\,u.

For fixed uu, expansion of the exponent gives

nlog⁡t−t=nlog⁡n−n−u22+O ⁣(∣u∣3n).n\log t-t = n\log n-n-\frac{u^2}{2} +O\!\left(\frac{|u|^3}{\sqrt n}\right).

Since dt=n dudt=\sqrt n\,du, the dominant contribution is approximately

nne−nn∫−∞∞e−u2/2 du.n^ne^{-n}\sqrt n \int_{-\infty}^{\infty}e^{-u^2/2}\,du.

The Gaussian integral equals 2π\sqrt{2\pi}, producing

n!∼2πn(n/e)n.n!\sim\sqrt{2\pi n}(n/e)^n.

This is an instance of Laplace's method: an integral whose integrand is sharply concentrated near a maximum is approximated by replacing its exponent locally with a quadratic function. A rigorous proof also controls the contribution away from that maximum.

Extension to the gamma function

For positive real xx, Stirling's formula extends to

Γ(x)∼2π xx−12e−x.\Gamma(x) \sim \sqrt{2\pi}\,x^{x-\frac12}e^{-x}.

Equivalently,

Γ(x+1)∼2πx(xe)x.\Gamma(x+1) \sim \sqrt{2\pi x}\left(\frac xe\right)^x.

These expressions must be distinguished carefully: Γ(x+1)=xΓ(x)\Gamma(x+1)=x\Gamma(x), so shifting the argument changes the power of xx.

For a complex variable zz, the logarithmic expansion is

log⁡Γ(z)∼(z−12)log⁡z−z+12log⁡(2π)+∑k=1∞B2k2k(2k−1)z2k−1.\log\Gamma(z) \sim \left(z-\frac12\right)\log z-z +\frac12\log(2\pi) + \sum_{k=1}^{\infty} \frac{B_{2k}}{2k(2k-1)z^{2k-1}}.

With consistent branches of the logarithms, this expansion holds uniformly in closed sectors

∣arg⁡z∣≤π−δ,δ>0,|\arg z|\leq\pi-\delta, \qquad \delta>0,

as ∣z∣→∞|z|\to\infty.

The sector restriction excludes a neighborhood of the negative real axis, where the gamma function has poles at the nonpositive integers and logarithmic branch issues become important. Error bounds from the positive real case do not transfer unchanged to arbitrary complex arguments.

Applications

Counting and combinatorics

Many quantities in combinatorics are factorial ratios. For a binomial coefficient, applying Stirling's formula to all three factorials gives

(nk)∼12πnp(1−p)exp⁡ ⁣(nH(p)),p=kn,\binom nk \sim \frac{1}{\sqrt{2\pi n p(1-p)}} \exp\!\left(nH(p)\right), \qquad p=\frac kn,

provided k→∞k\to\infty and n−k→∞n-k\to\infty. Here

H(p)=−plog⁡p−(1−p)log⁡(1−p)H(p)=-p\log p-(1-p)\log(1-p)

is binary entropy measured using natural logarithms.

When pp remains bounded away from 00 and 11, the approximation is particularly straightforward. If kk stays fixed while nn grows, replacing k!k! by its leading Stirling approximation does not give a relative error tending to zero.

A notable special case is the central binomial coefficient:

(2nn)∼4nπn.\binom{2n}{n}\sim\frac{4^n}{\sqrt{\pi n}}.

Such estimates describe the growth of many combinatorial sequences.

Probability and statistics

Stirling's approximation converts discrete probabilities involving factorials into tractable expressions. For a binomial distribution with fixed success probability p∈(0,1)p\in(0,1), it leads to the local Gaussian approximation

Pr⁡(X=k)∼12πnp(1−p)exp⁡ ⁣(−(k−np)22np(1−p))\Pr(X=k) \sim \frac{1}{\sqrt{2\pi np(1-p)}} \exp\!\left( -\frac{(k-np)^2}{2np(1-p)} \right)

as n→∞n\to\infty, when k−np=O(n)k-np=O(\sqrt n).

This connects factorial estimates with the normal distribution and the central limit theorem. The displayed approximation concerns individual probability masses in the central region; it is not automatically a relative-error approximation in far tails.

The formula also appears in calculations involving the Poisson and multinomial distributions, likelihoods, and asymptotic normalization constants.

Numerical computation

Factorials grow too rapidly for direct representation in many standard floating-point formats. Computing

log⁡(n!)≈(n+12)log⁡n−n+12log⁡(2π)+112n−1360n3\log(n!) \approx \left(n+\frac12\right)\log n-n +\frac12\log(2\pi) +\frac{1}{12n} -\frac{1}{360n^3}

avoids forming the enormous value of n!n! itself.

Logarithmic calculations are especially useful for products and ratios of factorials, such as binomial probabilities and likelihood functions. However, subtracting several large, nearly equal logarithms can still cause cancellation and loss of accuracy. Reliable implementations therefore combine asymptotic formulas, argument shifting through the gamma recurrence, and methods designed for numerical stability.

Accuracy and limitations

The leading approximation has relative error

n!2πn(n/e)n−1=112n+O(n−2).\frac{n!}{\sqrt{2\pi n}(n/e)^n}-1 = \frac{1}{12n}+O(n^{-2}).

Consequently, its accuracy improves at roughly the rate 1/n1/n. Including the factor 1+1/(12n)1+1/(12n) reduces the relative error to order n−2n^{-2}.

Several distinctions are important:

  • Large arguments are required for asymptotic accuracy. Exact inequalities remain valid for small positive integers, but a truncated approximation may still have substantial relative error.
  • Absolute and relative errors behave differently. A small relative error in a huge factorial can correspond to a very large absolute discrepancy.
  • More terms do not always mean better accuracy. The correction series is asymptotic rather than convergent.
  • Approximating each factorial requires checking each argument. In a ratio such as n!/[k!(n−k)!]n!/[k!(n-k)!], large nn alone does not ensure that kk and n−kn-k are large.
  • Complex arguments require domain and branch control. The positive-real error bounds cannot be used indiscriminately throughout the complex plane.