Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I found a question while I was trying to practice Combinatorics and Probabilistic methods.I tried to solve it with no success.. this is the question:

Use the Stirling approximation of the factorial to show that for every $0\leq p \leq 1$ there holds

$$\lim _{n\to \infty}\frac{1}{n}\log\binom{n}{pn}=H(p)$$ where $H(p)=-p\log(p) -(1-p)\log(1-p)$ is the binary entropy function.

Any help?

share|cite|improve this question
Is there a combinatorial / information-theoretic intepretation of this, does anyone know? – ShreevatsaR Apr 13 '13 at 11:30
@ShreevatsaR yes, it says that coding a uniform subset, $pn$ of $n$ (lhs), asymptotically requires as many bits as coding a sampling from $n$ elements where each element is picked with change $p$ (rhs). – Thomas Ahle Dec 14 '15 at 14:31

Let $q=1-p$.

The Stirling approximation asserts $n! \sim (\frac{n}{e})^{n} \sqrt{2\pi n}$. This gives:

$$\binom{n}{pn} \sim \frac{(n/e)^{n}}{(np/e)^{np}(nq/e)^{nq}}\frac{\sqrt{2\pi n}}{\sqrt{2\pi np}\sqrt{2\pi nq}}$$

The $(n/e)^n$ cancels with $(n/e)^{np}(n/e)^{nq}$, so this simplifies to:

$$\binom{n}{pn} \sim \frac{1}{p^{np}q^{nq}}\frac{1}{\sqrt{2\pi npq}}$$ Upon taking logarithm in base 2, we get:

$$\log_2\binom{n}{pn} \sim -n (p\log_2 p + q \log_2 q) - \log_2 (2\pi n pq)/2$$ Dividing by $n$, it transforms to:

$$\frac{1}{n}\log_2\binom{n}{pn} \sim -(p\log_2 p + q \log_2 q) - \log_2 (2\pi n pq)/(2n) = H(p) + O(\ln n/ n)$$ And when $n$ tends to infinity, we get the desired limit.

EDIT: You don't need the full strength of Stirling approximation. $n! = (n/e)^{n} g(n)$ where $n^{\alpha} \le g \le n^{\beta}$ is enough.

share|cite|improve this answer
It is not by chance that taking the sum of independant bernoulli, we converge to the exponentiated entropy of such bernoulli..... – nicolas Oct 26 '13 at 21:04

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.