# §26.3 Lattice Paths: Binomial Coefficients

## §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)$. See also 1.2(i). 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$, Symbols: $\binom{\NVar{m}}{\NVar{n}}$: binomial coefficient, $!$: factorial (as in $n!$), $m$: nonnegative integer and $n$: nonnegative integer A&S Ref: 24.1.1 Permalink: http://dlmf.nist.gov/26.3.E1 Encodings: TeX, pMML, png See also: Annotations for 26.3(i)
 26.3.2 $\binom{m}{n}=0,$ $n>m$. Symbols: $\binom{\NVar{m}}{\NVar{n}}$: binomial coefficient, $m$: nonnegative integer and $n$: nonnegative integer Permalink: http://dlmf.nist.gov/26.3.E2 Encodings: TeX, pMML, png See also: Annotations for 26.3(i)

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$, Symbols: $\binom{\NVar{m}}{\NVar{n}}$: binomial coefficient, $x$: real variable, $m$: nonnegative integer and $n$: nonnegative integer A&S Ref: 24.1.1 Permalink: http://dlmf.nist.gov/26.3.E3 Encodings: TeX, pMML, png See also: Annotations for 26.3(ii)
 26.3.4 $\sum_{m=0}^{\infty}\binom{m+n}{m}x^{m}=\frac{1}{(1-x)^{n+1}},$ $|x|<1$. Symbols: $\binom{\NVar{m}}{\NVar{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 See also: Annotations for 26.3(ii)

## §26.3(iii) Recurrence Relations

 26.3.5 $\displaystyle\binom{m}{n}$ $\displaystyle=\binom{m-1}{n}+\genfrac{(}{)}{0.0pt}{}{m-1}{n-1},$ $m\geq n\geq 1$, Symbols: $\binom{\NVar{m}}{\NVar{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 See also: Annotations for 26.3(iii) 26.3.6 $\displaystyle\binom{m}{n}$ $\displaystyle=\frac{m}{n}\binom{m-1}{n-1}=\frac{m-n+1}{n}\binom{m}{n-1},$ $m\geq n\geq 1$, Symbols: $\binom{\NVar{m}}{\NVar{n}}$: binomial coefficient, $m$: nonnegative integer and $n$: nonnegative integer Permalink: http://dlmf.nist.gov/26.3.E6 Encodings: TeX, pMML, png See also: Annotations for 26.3(iii)
 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$. Symbols: $\binom{\NVar{m}}{\NVar{n}}$: binomial coefficient, $k$: nonnegative integer, $m$: nonnegative integer and $n$: nonnegative integer A&S Ref: 24.1.1 Permalink: http://dlmf.nist.gov/26.3.E8 Encodings: TeX, pMML, png See also: Annotations for 26.3(iii)

## §26.3(iv) Identities

 26.3.9 $\binom{n}{0}=\binom{n}{n}=1,$ Symbols: $\binom{\NVar{m}}{\NVar{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 See also: Annotations for 26.3(iv)
 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{\NVar{m}}{\NVar{n}}$: binomial coefficient, $!$: factorial (as in $n!$) and $n$: nonnegative integer A&S Ref: 24.1.1 Permalink: http://dlmf.nist.gov/26.3.E11 Encodings: TeX, pMML, png See also: Annotations for 26.3(iv)

 26.3.12 $\binom{2n}{n}\sim\frac{4^{n}}{\sqrt{\pi n}},$ $n\to\infty$. Symbols: $\sim$: asymptotic equality, $\binom{\NVar{m}}{\NVar{n}}$: binomial coefficient, $\pi$: the ratio of the circumference of a circle to its diameter and $n$: nonnegative integer Referenced by: §26.5(iv) Permalink: http://dlmf.nist.gov/26.3.E12 Encodings: TeX, pMML, png See also: Annotations for 26.3(v)