# §26.5 Lattice Paths: Catalan Numbers

## §26.5(i) Definitions

$\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(\NVar{n}\right)$: Catalan number Symbols: $\binom{\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)

(Sixty-six equivalent definitions of $\mathop{C\/}\nolimits\!\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}\mathop{C\/}\nolimits\!\left(n\right)x^{n}=\frac{1-\sqrt{1-% 4x}}{2x},$ $|x|<\tfrac{1}{4}$. Symbols: $\mathop{C\/}\nolimits\!\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(iii) Recurrence Relations

 26.5.3 $\displaystyle\mathop{C\/}\nolimits\!\left(n+1\right)$ $\displaystyle=\sum_{k=0}^{n}\mathop{C\/}\nolimits\!\left(k\right)\mathop{C\/}% \nolimits\!\left(n-k\right),$ Symbols: $\mathop{C\/}\nolimits\!\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.4 $\displaystyle\mathop{C\/}\nolimits\!\left(n+1\right)$ $\displaystyle=\frac{2(2n+1)}{n+2}\mathop{C\/}\nolimits\!\left(n\right),$ Symbols: $\mathop{C\/}\nolimits\!\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.5 $\displaystyle\mathop{C\/}\nolimits\!\left(n+1\right)$ $\displaystyle=\sum_{k=0}^{\left\lfloor n/2\right\rfloor}\binom{n}{2k}2^{n-2k}% \mathop{C\/}\nolimits\!\left(k\right).$

## §26.5(iv) Limiting Forms

 26.5.6 $\mathop{C\/}\nolimits\!\left(n\right)\sim\frac{4^{n}}{\sqrt{\pi n^{3}}},$ $n\to\infty$,
 26.5.7 $\lim_{n\to\infty}\frac{\mathop{C\/}\nolimits\!\left(n+1\right)}{\mathop{C\/}% \nolimits\!\left(n\right)}=4.$ Symbols: $\mathop{C\/}\nolimits\!\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)