6.3 Factorial Approximations

Many probability calculations involve factorials. As discussed in Section 6.2, factorials are often hard to work with. This section introduces a method for approximating factorials using simpler functions. These approximations make it easier to answer questions like, “how big is $n!$?”, or "how big is $n \text{ choose } k$?", when $n$ and $k$ are large.

Consider the definition of the factorial:

This product involves $n$ terms. The early terms all are of size $n$. So, to a very rough approximation, $n! \approx n^n$. Clearly $n! < n^n$ since all of the terms in the product except the first are less than $n$. Half are larger than $n/2$ and half are smaller, so a better approximation is $(n/2)^n$. Stirling’s approximation provides an accurate estimate for $n!$ using a function roughly of the form $(n/e)^n$.

Stirling’s approximation is remarkably accurate, even for relatively small $n$. Here’s a table comparing values. The values for the approximation have been rounded to the tenth’s place.

Notice that, while the absolute error in the approximation grows as $n$ increases, the relative error is vanishing. The table below provides the errors, printed to their first significant figure.

Stirling’s approximation has less than a 2% error for $n \geq 5$, and less than a 1% error for $n \geq 9$.