The Catalan Numbers

Statement

Given a number n, find the $n^{th}$ Catalan number.

Catalan numbers are a special sequence of numbers given by the following set of formulas:

$C_0 = 1$

$C_n = \sum_{i=0}^{n-1} C_iC_{n-1-i}$

The first expression gives the base case of the formula. The second expression says that the $n^{th}$ Catalan number is simply the sum of products of specific Catalan number pairs. These specific pairs are just Catalan numbers with the same distance from either end of the series.

$C_4$ for example would be equal to:

$C_4 = C_0C_3 + C_1C_2 + C_2C_1 + C_3C_0$ ...