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 objects from a collection of distinct objects without regard to order. $\genfrac{(}{)}{0.0pt}{}{m+n}{n}$ is the number of lattice paths from to . See also 1.2(i). The number of lattice paths from to , $m\leq n$ , that stay on or above the line 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 ), : nonnegative integer and : 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,$

ⓘ

Symbols:: $\genfrac{(}{)}{0.0pt}{}{\NVar{m}}{\NVar{n}}$ : binomial coefficient, : nonnegative integer and : 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}$ .


	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, : nonnegative integer and : 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.


	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, : nonnegative integer and : 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, : real variable, : nonnegative integer and : 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}},$

ⓘ

Symbols:: $\genfrac{(}{)}{0.0pt}{}{\NVar{m}}{\NVar{n}}$ : binomial coefficient, : real variable, : nonnegative integer and : 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 $\genfrac{(}{)}{0.0pt}{}{m}{n}=\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, : nonnegative integer and : 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 $\genfrac{(}{)}{0.0pt}{}{m}{n}=\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, : nonnegative integer and : 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, : nonnegative integer, : nonnegative integer and : 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, : nonnegative integer, : nonnegative integer and : 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 : 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, : nonnegative integer, : nonnegative integer and : 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 ) and : 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 : 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

26.2 Basic Definitions 26.4 Lattice Paths: Multinomial Coefficients and Set Partitions

Site Privacy Accessibility Privacy Program Copyrights Vulnerability Disclosure No Fear Act Policy FOIA Environmental Policy Scientific Integrity Information Quality Standards Commerce.gov Science.gov USA.gov


	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


	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