Lesson 3

Good approximations of binomial coefficients can be obtained using Stirling's formula: \[n! \sim \sqrt{2\pi n}\left(\frac{n}{e}\right)^{n} \text{ or }n! =\Theta\left(\sqrt n\left(\frac{n}{e}\right)^{n}\right) \ .\] The symbol \(\sim\) means that the ratio approaches one as \(n\) grows.

For example, when \(n\) is even, it gives the following estimate for the central binomial coefficient: \[\binom{n}{\frac{n}{2}}=\Theta\left(\frac{2^n}{\sqrt{n}}\right) \ .\] More generally, for any constant \(0 < \alpha < 1\) and integers \(n\) such that \(\alpha n\) is an integer, the following holds: \[\binom{n}{\alpha n}=\Theta\left(\frac{2^{n\cdot H(\alpha)}}{\sqrt n}\right)\ ,\] where \(H(\alpha)=-\alpha\log_{2}\alpha-(1-\alpha)\log_{2}(1-\alpha)\) is entropy, its graph is shown below.