# Approximating the logarithm of the binomial coefficient

We know that by using Stirling approximation: $\log n! \approx n \log n$

So how to approximate $\log {m \choose n}$?

-

A better approximation for the logarithm of a factorial can be found by using $\log n! \approx n \log n - n$. Interestingly, the additional terms in the approximation of the binomial coefficient cancel out, and the result is the same as if you used the simpler approximation $\log n! \approx n\log n$:

\begin{align} \log {n\choose m} & = \log \frac{n!}{m!(n-m)!} \\ & = \log n! - \log m! - \log (n-m)! \\ & \approx n \log n - n - m \log m + m - (n-m) \log (n-m) + n-m \\ & = n \log n - m \log m - (n - m) \log (n-m) \end{align}

An even better approximation uses more terms of Stirling's approximation, giving $\log n! \approx (n+\tfrac{1}{2})\log n - n + \tfrac{1}{2}\log 2\pi$ and hence

\begin{align} \log {n\choose m} &\approx (n+\tfrac{1}{2})\log n - (m+\tfrac{1}{2})\log m - (n-m+\tfrac{1}{2})\log (n-m) - \tfrac{1}{2}\log 2\pi \\ & = n\log n - m \log m - (n-m)\log(n-m) + \cdots \\ & \qquad +\tfrac{1}{2} (\log n - \log m - \log (n-m) - \log 2\pi) \end{align}

where the last term is the correction from using more terms of Stirling's approximation.

-

Using $\log(n!) ≈ n \log(n)$ and the definition of the binomial coefficient, $\log{m \choose n} ≈ m \log{m} - (m-n) \log{(m-n)} - n \log{n}$. The same should work for any of the more precise statements of Stirling's approximation.

-

If you expand stirling's approximation for $n\choose\alpha n$, you may also notice that it can be written as $$H(a) - 1/2\log(2\pi\, n\alpha(1-\alpha))$$ Where $$H(a) = \alpha n \log(1/\alpha) -(1 - \alpha) n \log(1/(1 - \alpha))$$ Is the binary entropy function (in nats).

If you further notice that $n\alpha(1-\alpha)$ is the variance of a binomial distribution, it becomes pretty easy to remember. (And you start to see how you might derive the central limit theorem for binomial distributions).

-