Stirling's Formula

In permutations, we showed that the number of permutations of $n$ distinct objects is given by the factorial function $n!$ How quickly does the factorial function $n!$ grow as a function of $n?$ This behavior is captured in the approximation known as Stirling's formula $($also known as Stirling's approximation$)$.

Stirling's Formula

The factorial function $n!$ is approximated by

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

Furthermore, for any positive integer $n$, we have the bounds

$\sqrt{2\pi}\ n^{n+{\small\frac12}}e^{-n} \le n! \le e\ n^{n+{\small\frac12}}e^{-n}.$

The theorem defined in binomial coefficient as ${ 2n \choose n } = \frac { (2n)!} {n!^2}$ for $n \geq 0$ and it approaches $\frac {4^n}{\sqrt{\pi n}}$ asymptotically.

Given Stirling's formula, we have

$\begin{aligned} n! &\approx \sqrt{2 \pi n} \left ( \frac {n}{e} \right )^n \\ (2n)! &\approx \sqrt{4 \pi n} \left ( \frac {2n}{e} \right )^{2n}. \end{aligned}$

Taking the ratio of the second approximation to the square of the first approximation,

$\frac {(2n)!}{n!^2} \implies \sqrt{ \frac {4\pi n}{ (2 \pi n)^2 } } \cdot \frac {(2n)^{2n}}{n^{2n}} \cdot \frac {e^{2n}}{e^{2n}} = \frac {1}{\sqrt{\pi n}} \cdot 2^{2n} = \frac {4^n}{\sqrt{\pi n}}.\ _\square$

Catalan number occurs many times in various counting problems; it is defined to be $\large C_n = \frac {1}{n+1} { 2n \choose n }$. For more information, go to Catalan Numbers.