Editing Binomial coefficient (section)

== Bounds and asymptotic formulas ==
The following bounds for <math>\tbinom n k</math> hold for all values of ''n'' and ''k'' such that {{math|1 ≤ ''k'' ≤ ''n''}}:
<math display="block">\frac{n^k}{k^k} \le {n \choose k} \le \frac{n^k}{k!} < \left(\frac{n\cdot e}{k}\right)^k.</math>
The first inequality follows from the fact that
<math display="block"> {n \choose k} = \frac{n}{k} \cdot \frac{n-1}{k-1} \cdots \frac{n-(k-1)}{1} </math>
and each of these <math>k </math> terms in this product is <math display="inline"> \geq \frac{n}{k} </math>. A similar argument can be made to show the second inequality. The final strict inequality is equivalent to <math display="inline">e^k > k^k / k!</math>, that is clear since the RHS is a term of the exponential series <math display="inline"> e^k = \sum_{j=0}^\infty k^j/j! </math>.

From the divisibility properties we can infer that
<math display="block">\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},</math>
where both equalities can be achieved.<ref name="Farhi2007" />

The following bounds are useful in information theory:<ref name=cover2006>{{cite book |author1=Thomas M. Cover |author2=Joy A. Thomas |title=Elements of Information Theory |date=18 July 2006 |publisher=Wiley |location=Hoboken, New Jersey |isbn=0-471-24195-4}}</ref>{{rp|353}}
<math display="block"> \frac{1}{n+1} 2^{nH(k/n)} \leq {n \choose k} \leq 2^{nH(k/n)} </math>
where <math>H(p) = -p\log_2(p) -(1-p)\log_2(1-p)</math> is the [[binary entropy function]]. It can be further tightened to
<math display="block"> \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)}</math>
for all <math>1 \leq k \leq n-1</math>.<ref name=macwilliams1977>{{cite book |author1=F. J. MacWilliams |author2=N. J. A. Sloane |title=The Theory of Error-Correcting Codes |volume=16 |edition=3rd |year=1981 |publisher=North-Holland |isbn=0-444-85009-0}}</ref>{{rp|309}}

=== Both ''n'' and ''k'' large ===
[[Stirling's approximation]] yields the following approximation, valid when <math>n-k,k</math> both tend to infinity:
<math display="block">{n \choose k} \sim
\sqrt{n\over 2\pi k (n-k)} \cdot
{n^n \over k^k (n-k)^{n-k}}
</math>
Because the inequality forms of Stirling's formula also bound the factorials, slight variants on the above asymptotic approximation give exact bounds.
In particular, when <math>n</math> is sufficiently large, one has
<math display="block"> {2n \choose n} \sim \frac{2^{2n}}{\sqrt{n\pi }}</math> and <math>\sqrt{n}{2n \choose n} \ge 2^{2n-1}</math>. More generally, for {{math|''m'' ≥ 2}} and {{math|''n'' ≥ 1}} (again, by applying Stirling's formula to the factorials in the binomial coefficient),
<math display="block">\sqrt{n}{mn \choose n} \ge \frac{m^{m(n-1)+1}}{(m-1)^{(m-1)(n-1)}}.</math>

If ''n'' is large and ''k'' is linear in ''n'', various precise asymptotic estimates exist for the binomial coefficient <math display="inline"> \binom{n}{k}</math>. For example, if <math>| n/2 - k | = o(n^{2/3})</math> then
<math display="block"> \binom{n}{k} \sim \binom{n}{\frac{n}{2}} e^{-d^2/(2n)} \sim \frac{2^n}{\sqrt{\frac{1}{2}n \pi }} e^{-d^2/(2n)}</math>
where ''d'' = ''n'' − 2''k''.<ref>{{cite book|title=Asymptopia|last1=Spencer|first1=Joel|last2=Florescu|first2=Laura|date=2014| publisher=[[American Mathematical Society|AMS]]|isbn=978-1-4704-0904-3|series=Student mathematical library|volume=71|page=66| oclc=865574788|author1-link=Joel Spencer}}</ref>

=== {{mvar|n}} much larger than {{mvar|k}} ===
If {{mvar|n}} is large and {{mvar|k}} is {{math|''o''(''n'')}} (that is, if {{math| ''k''/''n'' → 0}}), then
<math display = block> \binom{n}{k} \sim \left(\frac{n e}{k} \right)^k \cdot (2\pi k)^{-1/2} \cdot \exp\left(- \frac{k^2}{2n}(1 + o(1))\right)</math>
where again {{mvar|o}} is the [[little o notation]].<ref>{{cite book|title=Asymptopia|last1=Spencer|first1=Joel| last2=Florescu|first2=Laura|date=2014|publisher=[[American Mathematical Society|AMS]]|isbn=978-1-4704-0904-3|series=Student mathematical library|volume=71|page=59|oclc=865574788|author1-link=Joel Spencer}}</ref>

=== Sums of binomial coefficients ===
A simple and rough upper bound for the sum of binomial coefficients can be obtained using the [[binomial theorem]]:
<math display="block">\sum_{i=0}^k {n \choose i} \leq \sum_{i=0}^k n^i\cdot 1^{k-i} \leq (1+n)^k</math>
More precise bounds are given by
<math display="block">\frac{1}{\sqrt{8n\varepsilon(1-\varepsilon)}} \cdot 2^{H(\varepsilon) \cdot n} \leq \sum_{i=0}^{k} \binom{n}{i} \leq 2^{H(\varepsilon) \cdot n},</math>
valid for all integers <math>n > k \geq 1</math> with <math>\varepsilon \doteq k/n \leq 1/2</math>.<ref>see e.g. {{harvtxt|Ash|1990|p=121}} or {{harvtxt|Flum|Grohe|2006|p=427}}.</ref>

=== Generalized binomial coefficients ===
The [[Gamma function#Euler's definition as an infinite product|infinite product formula for the gamma function]] also gives an expression for binomial coefficients
<math display="block">(-1)^k {z \choose k}= {-z+k-1 \choose k} = \frac{1}{\Gamma(-z)} \frac{1}{(k+1)^{z+1}} \prod_{j=k+1} \frac{\left(1+\frac{1}{j}\right)^{-z-1}}{1-\frac{z+1}{j}}</math>
which yields the asymptotic formulas
<math display="block">{z \choose k} \approx \frac{(-1)^k}{\Gamma(-z) k^{z+1}} \qquad \text{and} \qquad {z+k \choose k} = \frac{k^z}{\Gamma(z+1)}\left( 1+\frac{z(z+1)}{2k}+\mathcal{O}\left(k^{-2}\right)\right)</math>
as <math>k \to \infty</math>.

This asymptotic behaviour is contained in the approximation
<math display="block">{z+k \choose k}\approx \frac{e^{z(H_k-\gamma)}}{\Gamma(z+1)}</math>
as well. (Here <math>H_k</math> is the ''k''-th [[harmonic number]] and <math>\gamma</math> is the [[Euler–Mascheroni constant]].)

Further, the asymptotic formula
<math display="block">\frac{{z+k\choose j}}{{k\choose j}}\to \left(1-\frac{j}{k}\right)^{-z}\quad\text{and}\quad \frac{{j\choose j-k}}{{j-z\choose j-k}}\to \left(\frac{j}{k}\right)^z</math>
hold true, whenever <math>k\to\infty</math> and <math>j/k \to x</math> for some complex number <math>x</math>.