# §26.3(i) Definitions

$\binom{m}{n}$ is the number of ways of choosing $n$ objects from a collection of $m$ distinct objects without regard to order. $\binom{m+n}{n}$ is the number of lattice paths from $(0,0)$ to $(m,n)$. The number of lattice paths from $(0,0)$ to $(m,n)$, $m\leq n$, that stay on or above the line $y=x$ is $\binom{m+n}{m}-\binom{m+n}{m-1}.$

 26.3.1 $\binom{m}{n}=\binom{m}{m-n}=\frac{m!}{(m-n)!\,n!},$ $m\geq n$,
 26.3.2 $\binom{m}{n}=0,$ $n>m$.

For numerical values of $\binom{m}{n}$ and $\binom{m+n}{n}$ see Tables 26.3.1 and 26.3.2.

# §26.3(ii) Generating Functions

 26.3.3 $\sum_{n=0}^{m}\binom{m}{n}x^{n}=(1+x)^{m},$ $m=0,1,\ldots$,
 26.3.4 $\sum_{m=0}^{\infty}\binom{m+n}{m}x^{m}=\frac{1}{(1-x)^{n+1}},$ $|x|<1$. Symbols: $\binom{m}{n}$: binomial coefficient, $x$: real variable, $m$: nonnegative integer and $n$: nonnegative integer A&S Ref: 24.1.1 (in slightly different form) Permalink: http://dlmf.nist.gov/26.3.E4 Encodings: TeX, pMML, png

# §26.3(iii) Recurrence Relations

 26.3.5 $\displaystyle\binom{m}{n}$ $\displaystyle=\binom{m-1}{n}+\binomial{m-1}{n-1},$ $m\geq n\geq 1$, Symbols: $\binom{m}{n}$: binomial coefficient, $m$: nonnegative integer and $n$: nonnegative integer A&S Ref: 24.1.1 Permalink: http://dlmf.nist.gov/26.3.E5 Encodings: TeX, pMML, png 26.3.6 $\displaystyle\binom{m}{n}$ $\displaystyle=\frac{m}{n}\binom{m-1}{n-1}$ $\displaystyle=\frac{m-n+1}{n}\binom{m}{n-1},$ $m\geq n\geq 1$,
 26.3.7 $\binom{m+1}{n+1}=\sum_{k=n}^{m}\binom{k}{n},$ $m\geq n\geq 0$,
 26.3.8 $\binom{m}{n}=\sum_{k=0}^{n}\binom{m-n-1+k}{k},$ $m\geq n\geq 0$.

# §26.3(iv) Identities

 26.3.9 $\binom{n}{0}=\binom{n}{n}=1,$ Symbols: $\binom{m}{n}$: binomial coefficient and $n$: nonnegative integer A&S Ref: 24.1.1 Permalink: http://dlmf.nist.gov/26.3.E9 Encodings: TeX, pMML, png
 26.3.10 $\binom{m}{n}=\sum_{k=0}^{n}(-1)^{n-k}\binom{m+1}{k},$ $m\geq n\geq 0$,
 26.3.11 $\binom{2n}{n}=\frac{2^{n}(2n-1)(2n-3)\cdots 3\cdot 1}{n!}.$ Symbols: $\binom{m}{n}$: binomial coefficient, $!$: $n!$: factorial and $n$: nonnegative integer A&S Ref: 24.1.1 Permalink: http://dlmf.nist.gov/26.3.E11 Encodings: TeX, pMML, png

 26.3.12 $\binom{2n}{n}\sim\frac{4^{n}}{\sqrt{\pi n}},$ $n\to\infty$. Symbols: $\binom{m}{n}$: binomial coefficient, $\sim$: asymptotic equality and $n$: nonnegative integer Referenced by: §26.5(iv) Permalink: http://dlmf.nist.gov/26.3.E12 Encodings: TeX, pMML, png