Stirling's approximation

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 ${\displaystyle n}$. It is named after James Stirling, though a related but less precise result was first stated by Abraham de Moivre.^[1][2][3]

One way of stating the approximation involves the logarithm of the factorial: $${\displaystyle \ln(n!)=n\ln n-n+O(\ln n),}$$ where the big O notation means that, for all sufficiently large values of ${\displaystyle n}$, the difference between ${\displaystyle \ln(n!)}$ and ${\displaystyle n\ln n-n}$ will be at most proportional to the logarithm. 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 $${\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 ${\displaystyle {\tfrac {1}{2}}\log(2\pi n)+O({\tfrac {1}{n}})}$, corresponding to an approximate formula for the factorial itself, $${\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, that their ratio tends to 1 as ${\displaystyle n}$ tends to infinity. The following version of the bound holds for all ${\displaystyle n\geq 1}$, rather than only asymptotically: $${\displaystyle {\sqrt {2\pi n}}\ \left({\frac {n}{e}}\right)^{n}e^{\left({\frac {1}{12n}}-{\frac {1}{360n^{3}}}\right)}<n!<{\sqrt {2\pi n}}\ \left({\frac {n}{e}}\right)^{n}e^{\frac {1}{12n}}.}$$