About the Project
26 Combinatorial AnalysisProperties

§26.5 Lattice Paths: Catalan Numbers

Contents
  1. §26.5(i) Definitions
  2. §26.5(ii) Generating Function
  3. §26.5(iii) Recurrence Relations
  4. §26.5(iv) Limiting Forms

§26.5(i) Definitions

C(n) is the Catalan number. It counts the number of lattice paths from (0,0) to (n,n) that stay on or above the line y=x.

26.5.1 C(n)=1n+1(2nn)=12n+1(2n+1n)=(2nn)(2nn1)=(2n1n)(2n1n+1).

(Sixty-six equivalent definitions of C(n) are given in Stanley (1999, pp. 219–229).)

See Table 26.5.1.

Table 26.5.1: Catalan numbers.
n C(n) n C(n) n C(n)
0 1 7 429 14 26 74440
1 1 8 1430 15 96 94845
2 2 9 4862 16 353 57670
3 5 10 16796 17 1296 44790
4 14 11 58786 18 4776 38700
5 42 12 2 08012 19 17672 63190
6 132 13 7 42900 20 65641 20420

§26.5(ii) Generating Function

26.5.2 n=0C(n)xn=114x2x,
|x|<14.

§26.5(iii) Recurrence Relations

26.5.3 C(n+1) =k=0nC(k)C(nk),
26.5.4 C(n+1) =2(2n+1)n+2C(n),
26.5.5 C(n+1) =k=0n/2(n2k)2n2kC(k).

§26.5(iv) Limiting Forms

26.5.7 limnC(n+1)C(n)=4.