About the Project
26 Combinatorial AnalysisProperties

§26.3 Lattice Paths: Binomial Coefficients

Contents
  1. §26.3(i) Definitions
  2. §26.3(ii) Generating Functions
  3. §26.3(iii) Recurrence Relations
  4. §26.3(iv) Identities
  5. §26.3(v) Limiting Form

§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). See also 1.2(i). 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+nm1).

26.3.1 (mn)=(mmn)=m!(mn)!n!,
mn,
26.3.2 (mn)=0,
n>m.

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(1x)n+1,
|x|<1.

§26.3(iii) Recurrence Relations

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

§26.3(iv) Identities

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

See also §1.2(i).

§26.3(v) Limiting Form

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