Catalan number

The Catalan numbers are a sequence of natural numbers that occur in various counting problems, often involving recursively defined objects. They are named after Eugène Catalan, though they were previously discovered in the 1730s by Minggatu.

The n-th Catalan number can be expressed directly in terms of the central binomial coefficients by

${\displaystyle C_{n}={\frac {1}{n+1}}{2n \choose n}={\frac {(2n)!}{(n+1)!\,n!}}\qquad {\text{for }}n\geq 0.}$

The first Catalan numbers for n = 0, 1, 2, 3, ... are

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, ... (sequence A000108 in the OEIS).