What's New
About the Project
NIST
26 Combinatorial AnalysisProperties

§26.3 Lattice Paths: Binomial Coefficients

Contents

§26.3(i) Definitions

(mn) is the number of ways of choosing n objects from a collection of m distinct objects without regard to order. (m+nn) is the number of lattice paths from (0,0) to (m,n). The number of lattice paths from (0,0) to (m,n), mn, that stay on or above the line y=x is (m+nm)-(m+nm-1).

26.3.1 (mn)=(mm-n)=m!(m-n)!n!,
mn,

For numerical values of (mn) and (m+nn) see Tables 26.3.1 and 26.3.2.

Table 26.3.1: Binomial coefficients (mn).
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
Table 26.3.2: Binomial coefficients (m+nm) for lattice paths.
m n
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

§26.3(ii) Generating Functions

26.3.3 n=0m(mn)xn=(1+x)m,
m=0,1,,
26.3.4 m=0(m+nm)xm=1(1-x)n+1,
|x|<1.

§26.3(iii) Recurrence Relations

26.3.5 (mn) =(m-1n)+(m-1n-1),
mn1,
26.3.6 (mn) =mn(m-1n-1)
=m-n+1n(mn-1),
mn1,
26.3.7 (m+1n+1)=k=nm(kn),
mn0,
26.3.8 (mn)=k=0n(m-n-1+kk),
mn0.

§26.3(iv) Identities

26.3.9 (n0)=(nn)=1,
26.3.10 (mn)=k=0n(-1)n-k(m+1k),
mn0,
26.3.11 (2nn)=2n(2n-1)(2n-3)31n!.

See also §1.2(i).

§26.3(v) Limiting Form

26.3.12 (2nn)4nπn,
n.