§26.3 Lattice Paths: Binomial Coefficients

Permalink:: http://dlmf.nist.gov/26.3

Contents

§26.3(i) Definitions
§26.3(ii) Generating Functions
§26.3(iii) Recurrence Relations
§26.3(iv) Identities
§26.3(v) Limiting Form

§26.3(i) Definitions

Notes:: See Comtet (1974, pp. 8, 22–23). Tables 26.3.1 and 26.3.2 are from Abramowitz and Stegun (1964, Table 24.1).
Keywords:: binomial coefficients
Permalink:: http://dlmf.nist.gov/26.3.i

$\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$ ,

Symbols:: $\binom{m}{n}$ : binomial coefficient, $!$ : $n!$ : factorial, $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

26.3.2 $\binom{m}{n}=0,$ $n>m$ .

Symbols:: $\binom{m}{n}$ : binomial coefficient, $m$ : nonnegative integer and $n$ : nonnegative integer
Permalink:: http://dlmf.nist.gov/26.3.E2
Encodings:: TeX, pMML, png

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

Table 26.3.1: Binomial coefficients $\binom{m}{n}$ .

$m$	$n$
$m$	0	1	2	3	4	5	6	7	8	9	10
0	1
1	1	1
2	1	2	1
3	1	3	3	1
4	1	4	6	4	1
5	1	5	10	10	5	1
6	1	6	15	20	15	6	1
7	1	7	21	35	35	21	7	1
8	1	8	28	56	70	56	28	8	1
9	1	9	36	84	126	126	84	36	9	1
10	1	10	45	120	210	252	210	120	45	10	1

Symbols:: $\binom{m}{n}$ : binomial coefficient, $m$ : nonnegative integer and $n$ : nonnegative integer
Keywords:: binomial coefficients
Referenced by:: §26.3(i), §26.3(i)
Permalink:: http://dlmf.nist.gov/26.3.T1

Table 26.3.2: Binomial coefficients $\binom{m+n}{m}$ for lattice paths.

$m$	$n$
$m$	0	1	2	3	4	5	6	7	8
0	1	1	1	1	1	1	1	1	1
1	1	2	3	4	5	6	7	8	9
2	1	3	6	10	15	21	28	36	45
3	1	4	10	20	35	56	84	120	165
4	1	5	15	35	70	126	210	330	495
5	1	6	21	56	126	252	462	792	1287
6	1	7	28	84	210	462	924	1716	3003
7	1	8	36	120	330	792	1716	3432	6435
8	1	9	45	165	495	1287	3003	6435	12870

Symbols:: $\binom{m}{n}$ : binomial coefficient, $m$ : nonnegative integer and $n$ : nonnegative integer
Keywords:: binomial coefficients
Referenced by:: §26.3(i), §26.3(i)
Permalink:: http://dlmf.nist.gov/26.3.T2

§26.3(ii) Generating Functions

Notes:: See Riordan (1958, pp. 7–11).
Keywords:: binomial coefficients
Permalink:: http://dlmf.nist.gov/26.3.ii

26.3.3 $\sum _{{n=0}}^{m}\binom{m}{n}x^{n}=(1+x)^{m},$ $m=0,1,\ldots$ ,

Symbols:: $\binom{m}{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

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

Notes:: See Riordan (1958, pp. 4–5) and Comtet (1974, p. 10).
Keywords:: binomial coefficients
Permalink:: http://dlmf.nist.gov/26.3.iii

26.3.5 $\binom{m}{n}=\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 $\binom{m}{n}=\frac{m}{n}\binom{m-1}{n-1}=\frac{m-n+1}{n}\binom{m}{n-1},$ $m\geq n\geq 1$ ,

Symbols:: $\binom{m}{n}$ : binomial coefficient, $m$ : nonnegative integer and $n$ : nonnegative integer
Permalink:: http://dlmf.nist.gov/26.3.E6
Encodings:: TeX, pMML, png

26.3.7 $\binom{m+1}{n+1}=\sum _{{k=n}}^{m}\binom{k}{n},$ $m\geq n\geq 0$ ,

Symbols:: $\binom{m}{n}$ : binomial coefficient, $k$ : nonnegative integer, $m$ : nonnegative integer and $n$ : nonnegative integer
Permalink:: http://dlmf.nist.gov/26.3.E7
Encodings:: TeX, pMML, png

26.3.8 $\binom{m}{n}=\sum _{{k=0}}^{n}\binom{m-n-1+k}{k},$ $m\geq n\geq 0$ .

Symbols:: $\binom{m}{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

§26.3(iv) Identities

Notes:: See Comtet (1974, p. 10).
Keywords:: binomial coefficients
Permalink:: http://dlmf.nist.gov/26.3.iv

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$ ,

Symbols:: $\binom{m}{n}$ : binomial coefficient, $k$ : nonnegative integer, $m$ : nonnegative integer and $n$ : nonnegative integer
Permalink:: http://dlmf.nist.gov/26.3.E10
Encodings:: TeX, pMML, png

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

See also §1.2(i).

§26.3(v) Limiting Form

Notes:: See Comtet (1974, p. 292) and (5.11.7).
Keywords:: binomial coefficients
Permalink:: http://dlmf.nist.gov/26.3.v

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