# §26.5 Lattice Paths: Catalan Numbers

## §26.5(i) Definitions

$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 26

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

See Table 26.5.1.

## §26.5(ii) Generating Function

 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 26

## §26.5(iii) Recurrence Relations

 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 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 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).$

## §26.5(iv) Limiting Forms

 26.5.6 $C\left(n\right)\sim\frac{4^{n}}{\sqrt{\pi n^{3}}},$ $n\to\infty$,
 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 26