26 Combinatorial Analysis Properties 26.2 Basic Definitions 26.4 Lattice Paths: Multinomial Coefficients and Set Partitions

§26.3 Lattice Paths: Binomial Coefficients

ⓘ

Referenced by:: §1.2(i), §1.2(i)
Permalink:: http://dlmf.nist.gov/26.3
See also:: Annotations for Ch.26

§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

ⓘ

Keywords:: binomial coefficients, relation to lattice paths
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).
Referenced by:: §1.2(i)
Permalink:: http://dlmf.nist.gov/26.3.i
See also:: Annotations for §26.3 and Ch.26

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

Table 26.3.1: Binomial coefficients

\genfrac{(}{)}{0.0pt}{}{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:: $\genfrac{(}{)}{0.0pt}{}{\NVar{m}}{\NVar{n}}$ : binomial coefficient, $m$ : nonnegative integer and $n$ : nonnegative integer
Keywords:: binomial coefficients, tables
Referenced by:: §26.3(i), §26.3(i)
Permalink:: http://dlmf.nist.gov/26.3.T1
See also:: Annotations for §26.3(i), §26.3 and Ch.26

Table 26.3.2: Binomial coefficients

\genfrac{(}{)}{0.0pt}{}{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:: $\genfrac{(}{)}{0.0pt}{}{\NVar{m}}{\NVar{n}}$ : binomial coefficient, $m$ : nonnegative integer and $n$ : nonnegative integer
Keywords:: binomial coefficients, tables
Referenced by:: §26.3(i), §26.3(i)
Permalink:: http://dlmf.nist.gov/26.3.T2
See also:: Annotations for §26.3(i), §26.3 and Ch.26

§26.3(ii) Generating Functions

ⓘ

Keywords:: binomial coefficients, generating functions
Notes:: See Riordan (1958, pp. 7–11).
Permalink:: http://dlmf.nist.gov/26.3.ii
See also:: Annotations for §26.3 and Ch.26

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

ⓘ

Keywords:: binomial coefficients, recurrence relations
Notes:: See Riordan (1958, pp. 4–5) and Comtet (1974, p. 10).
Permalink:: http://dlmf.nist.gov/26.3.iii
See also:: Annotations for §26.3 and Ch.26

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$ ,
ⓘ Symbols: $\genfrac{(}{)}{0.0pt}{}{\NVar{m}}{\NVar{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 See also: Annotations for §26.3(iii), §26.3 and Ch.26

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

ⓘ

Keywords:: binomial coefficients, identities
Notes:: See Comtet (1974, p. 10).
Permalink:: http://dlmf.nist.gov/26.3.iv
See also:: Annotations for §26.3 and Ch.26

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$ ,
ⓘ Symbols: $\genfrac{(}{)}{0.0pt}{}{\NVar{m}}{\NVar{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 See also: Annotations for §26.3(iv), §26.3 and Ch.26

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(v) Limiting Form

ⓘ

Keywords:: binomial coefficients, limiting form
Notes:: See Comtet (1974, p. 292) and (5.11.7).
Permalink:: http://dlmf.nist.gov/26.3.v
See also:: Annotations for §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

© 2010–2020 NIST / Privacy Policy / Disclaimer / Feedback; Version 1.1.0; Release date 2020-12-15. A printed companion is available. 26.2 Basic Definitions 26.4 Lattice Paths: Multinomial Coefficients and Set Partitions

$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

$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