What's New
About the Project
NIST
26 Combinatorial AnalysisProperties

§26.5 Lattice Paths: Catalan Numbers

Contents

§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)-(2nn-1)=(2n-1n)-(2n-1n+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=1-1-4x2x,
|x|<14.

§26.5(iii) Recurrence Relations

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

§26.5(iv) Limiting Forms

26.5.6 C(n)4nπn3,
n,
26.5.7 limnC(n+1)C(n)=4.