Binomial coefficient
Bounds and asymptotic formulas

The following bounds for (n k) {\displaystyle {\tbinom {n}{k}}} hold for all values of n and k such that 1 ≤ k ≤ n: n k k k ≤ (n k) ≤ n k k ! < (n ⋅ e k) k. {\displaystyle {\frac {n^{k}}{k^{k}}}\leq {n \choose k}\leq {\frac {n^{k}}{k!}}<\left({\frac {n\cdot e}{k}}\right)^{k}.} The first inequality follows from the fact that (n k) = n k ⋅ n − 1 k − 1 ⋯ n − (k − 1) 1 {\displaystyle {n \choose k}={\frac {n}{k}}\cdot {\frac {n-1}{k-1}}\cdots {\frac {n-(k-1)}{1}}} and each of these k {\displaystyle k} terms in this product is ≥ n k {\textstyle \geq {\frac {n}{k}}}. A similar argument can be made to show the second inequality. The final strict inequality is equivalent to e k > k k / k ! {\textstyle e^{k}>k^{k}/k!}, that is clear since the RHS is a term of the exponential series e k = ∑ j = 0 ∞ k j / j ! {\textstyle e^{k}=\sum _{j=0}^{\infty }k^{j}/j!}.

From the divisibility properties we can infer that lcm (n − k, …, n) (n − k) ⋅ lcm ((k 0), …, (k k)) ≤ (n k) ≤ lcm (n − k, …, n) n − k, {\displaystyle {\frac {\operatorname {lcm} (n-k,\ldots,n)}{(n-k)\cdot \operatorname {lcm} \left({\binom {k}{0}},\ldots,{\binom {k}{k}}\right)}}\leq {\binom {n}{k}}\leq {\frac {\operatorname {lcm} (n-k,\ldots,n)}{n-k}},} where both equalities can be achieved.

The following bounds are useful in information theory: 1 n + 1 2 n H (k / n) ≤ (n k) ≤ 2 n H (k / n) {\displaystyle {\frac {1}{n+1}}2^{nH(k/n)}\leq {n \choose k}\leq 2^{nH(k/n)}} where H (p) = − p log 2 (p) − (1 − p) log 2 (1 − p) {\displaystyle H(p)=-p\log _{2}(p)-(1-p)\log _{2}(1-p)} is the binary entropy function. It can be further tightened to n 8 k (n − k) 2 n H (k / n) ≤ (n k) ≤ n 2 π k (n − k) 2 n H (k / n) {\displaystyle {\sqrt {\frac {n}{8k(n-k)}}}2^{nH(k/n)}\leq {n \choose k}\leq {\sqrt {\frac {n}{2\pi k(n-k)}}}2^{nH(k/n)}} for all 1 ≤ k ≤ n − 1 {\displaystyle 1\leq k\leq n-1}.
detectable_content:postscript