Catalan number

In combinatorial mathematics, the Catalan numbers form a sequence of natural numbers that occur in various counting problems, often involving recursively-defined objects. They are named after the Belgian mathematician Eugène Charles Catalan (1814–1894).

Using zero-based numbering, the nth Catalan number is given directly in terms of binomial coefficients by

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

An alternative expression for C_n is

which is equivalent to the expression given above because ${\displaystyle {\tbinom {2n}{n+1}}={\tfrac {n}{n+1}}{\tbinom {2n}{n}}}$. This shows that C_n is an integer, which is not immediately obvious from the first formula given. This expression forms the basis for a proof of the correctness of the formula.

...
Wikipedia