§26.5 Lattice Paths: Catalan Numbers

ⓘ

§26.5(i) Definitions

ⓘ

Keywords:: Catalan numbers, definitions, relation to lattice paths
Notes:: See Comtet (1974, pp. 52–54). Table 26.5.1 was computed by the author.
Permalink:: http://dlmf.nist.gov/26.5.i
See also:: Annotations for §26.5 and Ch.26

$C\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		$C\left(n\right)=\frac{1}{n+1}\genfrac{(}{)}{0.0pt}{}{2n}{n}=\frac{1}{2n+1}% \genfrac{(}{)}{0.0pt}{}{2n+1}{n}=\genfrac{(}{)}{0.0pt}{}{2n}{n}-\genfrac{(}{)}% {0.0pt}{}{2n}{n-1}=\genfrac{(}{)}{0.0pt}{}{2n-1}{n}-\genfrac{(}{)}{0.0pt}{}{2n% -1}{n+1}.$
ⓘ Defines: $C\left(\NVar{n}\right)$ : Catalan number Symbols: $\genfrac{(}{)}{0.0pt}{}{\NVar{m}}{\NVar{n}}$ : binomial coefficient and $n$ : nonnegative integer Referenced by: §26.5(iv) Permalink: http://dlmf.nist.gov/26.5.E1 Encodings: TeX, pMML, png See also: Annotations for §26.5(i), §26.5 and Ch.26

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

See Table 26.5.1.

Table 26.5.1: Catalan numbers.

$n$	$C\left(n\right)$	$n$	$C\left(n\right)$	$n$	$C\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:: $C\left(\NVar{n}\right)$ : Catalan number and $n$ : nonnegative integer
Keywords:: Catalan numbers, table
Referenced by:: §26.5(i), §26.5(i)
Permalink:: http://dlmf.nist.gov/26.5.T1
See also:: Annotations for §26.5(i), §26.5 and Ch.26

ⓘ

26.5.2		$\sum_{n=0}^{\infty}C\left(n\right)x^{n}=\frac{1-\sqrt{1-4x}}{2x},$
$\|x\|<\tfrac{1}{4}$ .
ⓘ Symbols: $C\left(\NVar{n}\right)$ : Catalan number, $x$ : real variable and $n$ : nonnegative integer Permalink: http://dlmf.nist.gov/26.5.E2 Encodings: TeX, pMML, png See also: Annotations for §26.5(ii), §26.5 and Ch.26

ⓘ

26.5.3	$\displaystyle C\left(n+1\right)$	$\displaystyle=\sum_{k=0}^{n}C\left(k\right)C\left(n-k\right),$
ⓘ Symbols: $C\left(\NVar{n}\right)$ : Catalan number, $k$ : nonnegative integer and $n$ : nonnegative integer Permalink: http://dlmf.nist.gov/26.5.E3 Encodings: TeX, pMML, png See also: Annotations for §26.5(iii), §26.5 and Ch.26
26.5.4	$\displaystyle C\left(n+1\right)$	$\displaystyle=\frac{2(2n+1)}{n+2}C\left(n\right),$
ⓘ Symbols: $C\left(\NVar{n}\right)$ : Catalan number and $n$ : nonnegative integer Permalink: http://dlmf.nist.gov/26.5.E4 Encodings: TeX, pMML, png See also: Annotations for §26.5(iii), §26.5 and Ch.26
26.5.5	$\displaystyle C\left(n+1\right)$	$\displaystyle=\sum_{k=0}^{\left\lfloor n/2\right\rfloor}\genfrac{(}{)}{0.0pt}{% }{n}{2k}2^{n-2k}C\left(k\right).$
ⓘ Symbols: $C\left(\NVar{n}\right)$ : Catalan number, $\genfrac{(}{)}{0.0pt}{}{\NVar{m}}{\NVar{n}}$ : binomial coefficient, $\left\lfloor\NVar{x}\right\rfloor$ : floor of $x$ , $k$ : nonnegative integer and $n$ : nonnegative integer Permalink: http://dlmf.nist.gov/26.5.E5 Encodings: TeX, pMML, png See also: Annotations for §26.5(iii), §26.5 and Ch.26

ⓘ

26.5.6		$C\left(n\right)\sim\frac{4^{n}}{\sqrt{\pi n^{3}}},$
$n\to\infty$ ,
ⓘ Symbols: $C\left(\NVar{n}\right)$ : Catalan number, $\sim$ : asymptotic equality, $\pi$ : the ratio of the circumference of a circle to its diameter and $n$ : nonnegative integer Permalink: http://dlmf.nist.gov/26.5.E6 Encodings: TeX, pMML, png See also: Annotations for §26.5(iv), §26.5 and Ch.26

26.5.7		$\lim_{n\to\infty}\frac{C\left(n+1\right)}{C\left(n\right)}=4.$
ⓘ Symbols: $C\left(\NVar{n}\right)$ : Catalan number and $n$ : nonnegative integer Permalink: http://dlmf.nist.gov/26.5.E7 Encodings: TeX, pMML, png See also: Annotations for §26.5(iv), §26.5 and Ch.26