This site is supported by donations to The OEIS Foundation.

# Catalan numbers

The Catalan numbers are also called Segner numbers.

(...)

## Formulae

${\displaystyle C_{n}={\frac {1}{n+1}}{\binom {2n}{n}},\quad n\geq 0,\,}$

where ${\displaystyle \scriptstyle {\binom {2n}{n}}\,}$ are central binomial coefficients.

## Recurrence relation

${\displaystyle C_{0}=1,\,}$
${\displaystyle C_{n}={\frac {2(2n-1)}{n+1}}~C_{n-1},\quad n\geq 1.\,}$

## Generating function

The ordinary generating function for the Catalan numbers is

${\displaystyle G_{\{C_{n}\}}(x)\equiv \sum _{n=0}^{\infty }C_{n}~x^{n}={\frac {1-{\sqrt {1-4x}}}{2x}}\,}$

which may be represented by the continued fraction

${\displaystyle G_{\{C_{n}\}}(x)={\frac {1}{1+{\underset {i=2}{\overset {\infty }{\rm {K}}}}~{\frac {-x}{1}}}}={\cfrac {1}{1-{\cfrac {x}{1-{\cfrac {x}{1-{\cfrac {x}{1-\ddots }}}}}}}}.\,}$

since ${\displaystyle \scriptstyle {\frac {1-{\sqrt {1-4x}}}{2x}}\,}$ is one of the two solutions of the quadratic functional equation

${\displaystyle x~{\big (}G_{\{C_{n}\}}(x){\big )}^{2}-G_{\{C_{n}\}}(x)+1=0.\,}$

(...)

## Forward differences

${\displaystyle C_{n+1}-C_{n}={\frac {3n}{n+2}}~C_{n},\quad n\geq 0.\,}$

## Partial sums

${\displaystyle \sum _{n=0}^{m}C_{n}=~?\,}$

## Partial sums of reciprocals

${\displaystyle \sum _{n=0}^{m}{\frac {1}{C_{n}}}=~?\,}$

## Sum of reciprocals

${\displaystyle \sum _{n=0}^{\infty }{\frac {1}{C_{n}}}=~?\,}$

## Sequences

Catalan numbers: ${\displaystyle \scriptstyle C_{n}\,}$ gives the count of balanced parenthesizations of ${\displaystyle \scriptstyle n,\,n\,\geq \,0,\,}$ "(" and ${\displaystyle \scriptstyle n,\,n\,\geq \,0,\,}$ ")" (represented by "1" and "0" respectively) (Cf. A000108)

{1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, ...} =
{#{ { } }, #{ {10} }, #{ {1010}, {1100} }, #{ {101010}, {101100}, {110010}, {110100}, {111000} }, #{ {10101010}, {10101100}, {10110010}, {10110100}, {10111000}, {11001010}, {11001100}, {11010010}, {11010100}, {11011000}, {11100010}, {11100100}, {11101000}, {11110000} }, ...}