Catalan numbers

This article page is a stub, please help by expanding it.

---

The Catalan numbers are also called Segner numbers.

Definitions

(...)

Formulae

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

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

Recurrence relation

$C_{0}=1,\,$

$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

$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

$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 $\scriptstyle {\frac {1-{\sqrt {1-4x}}}{2x}}\,$ is one of the two solutions of the quadratic functional equation

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

Order of basis

(...)

Forward differences

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

Partial sums

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

Partial sums of reciprocals

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

Sum of reciprocals

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

Sequences

Catalan numbers: $\scriptstyle C_{n}\,$ gives the count of balanced parenthesizations of $\scriptstyle n,\,n\,\geq \,0,\,$ "(" and $\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} }, ...}

See also

• Catalan triangle
• Combinatorial interpretations of Catalan numbers