# §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(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.

# §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}$.

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