§26.3 Lattice Paths: Binomial Coefficients

§26.3(i) Definitions

$\genfrac{(}{)}{0.0pt}{}{m}{n}$ is the number of ways of choosing $n$ objects from a collection of $m$ distinct objects without regard to order. $\genfrac{(}{)}{0.0pt}{}{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 $\genfrac{(}{)}{0.0pt}{}{m+n}{m}-\genfrac{(}{)}{0.0pt}{}{m+n}{m-1}.$

 26.3.1 $\genfrac{(}{)}{0.0pt}{}{m}{n}=\genfrac{(}{)}{0.0pt}{}{m}{m-n}=\frac{m!}{(m-n)!% \,n!},$ $m\geq n$, ⓘ Symbols: $\genfrac{(}{)}{0.0pt}{}{\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 and Ch.26
 26.3.2 $\genfrac{(}{)}{0.0pt}{}{m}{n}=0,$ $n>m$. ⓘ Symbols: $\genfrac{(}{)}{0.0pt}{}{\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), §26.3 and Ch.26

For numerical values of $\genfrac{(}{)}{0.0pt}{}{m}{n}$ and $\genfrac{(}{)}{0.0pt}{}{m+n}{n}$ see Tables 26.3.1 and 26.3.2.

§26.3(ii) Generating Functions

 26.3.3 $\sum_{n=0}^{m}\genfrac{(}{)}{0.0pt}{}{m}{n}x^{n}=(1+x)^{m},$ $m=0,1,\dotsc$, ⓘ Symbols: $\genfrac{(}{)}{0.0pt}{}{\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 and Ch.26
 26.3.4 $\sum_{m=0}^{\infty}\genfrac{(}{)}{0.0pt}{}{m+n}{m}x^{m}=\frac{1}{(1-x)^{n+1}},$ $|x|<1$. ⓘ Symbols: $\genfrac{(}{)}{0.0pt}{}{\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 and Ch.26

§26.3(iii) Recurrence Relations

 26.3.5 $\displaystyle\genfrac{(}{)}{0.0pt}{}{m}{n}$ $\displaystyle=\genfrac{(}{)}{0.0pt}{}{m-1}{n}+\genfrac{(}{)}{0.0pt}{}{m-1}{n-1},$ $m\geq n\geq 1$, ⓘ Symbols: $\genfrac{(}{)}{0.0pt}{}{\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 and Ch.26 26.3.6 $\displaystyle\genfrac{(}{)}{0.0pt}{}{m}{n}$ $\displaystyle=\frac{m}{n}\genfrac{(}{)}{0.0pt}{}{m-1}{n-1}=\frac{m-n+1}{n}% \genfrac{(}{)}{0.0pt}{}{m}{n-1},$ $m\geq n\geq 1$, ⓘ Symbols: $\genfrac{(}{)}{0.0pt}{}{\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 and Ch.26
 26.3.7 $\genfrac{(}{)}{0.0pt}{}{m+1}{n+1}=\sum_{k=n}^{m}\genfrac{(}{)}{0.0pt}{}{k}{n},$ $m\geq n\geq 0$, ⓘ
 26.3.8 $\genfrac{(}{)}{0.0pt}{}{m}{n}=\sum_{k=0}^{n}\genfrac{(}{)}{0.0pt}{}{m-n-1+k}{k},$ $m\geq n\geq 0$. ⓘ Symbols: $\genfrac{(}{)}{0.0pt}{}{\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 and Ch.26

§26.3(iv) Identities

 26.3.9 $\genfrac{(}{)}{0.0pt}{}{n}{0}=\genfrac{(}{)}{0.0pt}{}{n}{n}=1,$ ⓘ Symbols: $\genfrac{(}{)}{0.0pt}{}{\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 and Ch.26
 26.3.10 $\genfrac{(}{)}{0.0pt}{}{m}{n}=\sum_{k=0}^{n}(-1)^{n-k}\genfrac{(}{)}{0.0pt}{}{% m+1}{k},$ $m\geq n\geq 0$, ⓘ
 26.3.11 $\genfrac{(}{)}{0.0pt}{}{2n}{n}=\frac{2^{n}(2n-1)(2n-3)\cdots 3\cdot 1}{n!}.$ ⓘ Symbols: $\genfrac{(}{)}{0.0pt}{}{\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 and Ch.26

 26.3.12 $\genfrac{(}{)}{0.0pt}{}{2n}{n}\sim\frac{4^{n}}{\sqrt{\pi n}},$ $n\to\infty$. ⓘ Symbols: $\sim$: asymptotic equality, $\genfrac{(}{)}{0.0pt}{}{\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), §26.3 and Ch.26