§26.5 Lattice Paths: Catalan Numbers

Permalink:: http://dlmf.nist.gov/26.5

§26.5(i) Definitions
§26.5(ii) Generating Function
§26.5(iii) Recurrence Relations
§26.5(iv) Limiting Forms

§26.5(i) Definitions

Notes:: See Comtet (1974, pp. 52–54). Table 26.5.1 was computed by the author.
Keywords:: Catalan numbers
Permalink:: http://dlmf.nist.gov/26.5.i

$\mathop{C\/}\nolimits\!\left(n\right)$ 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 $\mathop{C\/}\nolimits\!\left(n\right)=\frac{1}{n+1}\binom{2n}{n}=\frac{1}{2n+1}\binom{2n+1}{n}=\binom{2n}{n}-\binom{2n}{n-1}=\binom{2n-1}{n}-\binom{2n-1}{n+1}.$

Defines:: $\mathop{C\/}\nolimits\!\left(n\right)$ : Catalan number
Symbols:: $\binom{m}{n}$ : binomial coefficient and $n$ : nonnegative integer
Referenced by:: §26.5(iv)
Permalink:: http://dlmf.nist.gov/26.5.E1
Encodings:: TeX, pMML, png

(Sixty-six equivalent definitions of $\mathop{C\/}\nolimits\!\left(n\right)$ are given in Stanley (1999, pp. 219–229).)

See Table 26.5.1.

Table 26.5.1: Catalan numbers.

$n$	$\mathop{C\/}\nolimits\!\left(n\right)$	$n$	$\mathop{C\/}\nolimits\!\left(n\right)$	$n$	$\mathop{C\/}\nolimits\!\left(n\right)$
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

Symbols:: $\mathop{C\/}\nolimits\!\left(n\right)$ : Catalan number and $n$ : nonnegative integer
Keywords:: Catalan numbers
Referenced by:: §26.5(i), §26.5(i)
Permalink:: http://dlmf.nist.gov/26.5.T1

§26.5(ii) Generating Function

Notes:: See Comtet (1974, pp. 52–53).
Keywords:: Catalan numbers
Permalink:: http://dlmf.nist.gov/26.5.ii

26.5.2 $\sum _{{n=0}}^{{\infty}}\mathop{C\/}\nolimits\!\left(n\right)x^{n}=\frac{1-\sqrt{1-4x}}{2x},$ $|x|<\tfrac{1}{4}$ .

Symbols:: $\mathop{C\/}\nolimits\!\left(n\right)$ : Catalan number, $x$ : real variable and $n$ : nonnegative integer
Permalink:: http://dlmf.nist.gov/26.5.E2
Encodings:: TeX, pMML, png

§26.5(iii) Recurrence Relations

Notes:: See Comtet (1974, p. 53), Riordan (1979, p. 157).
Keywords:: Catalan numbers
Permalink:: http://dlmf.nist.gov/26.5.iii

26.5.3 $\mathop{C\/}\nolimits\!\left(n+1\right)=\sum _{{k=0}}^{{n}}\mathop{C\/}\nolimits\!\left(k\right)\mathop{C\/}\nolimits\!\left(n-k\right),$

Symbols:: $\mathop{C\/}\nolimits\!\left(n\right)$ : Catalan number, $k$ : nonnegative integer and $n$ : nonnegative integer
Permalink:: http://dlmf.nist.gov/26.5.E3
Encodings:: TeX, pMML, png

26.5.4 $\mathop{C\/}\nolimits\!\left(n+1\right)=\frac{2(2n+1)}{n+2}\mathop{C\/}\nolimits\!\left(n\right),$

Symbols:: $\mathop{C\/}\nolimits\!\left(n\right)$ : Catalan number and $n$ : nonnegative integer
Permalink:: http://dlmf.nist.gov/26.5.E4
Encodings:: TeX, pMML, png

26.5.5 $\mathop{C\/}\nolimits\!\left(n+1\right)=\sum _{{k=0}}^{{\left\lfloor n/2\right\rfloor}}\binom{n}{2k}2^{{n-2k}}\mathop{C\/}\nolimits\!\left(k\right).$