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$

$C_4 = (1)(5) + (1)(2) + (2)(1) + (5)(1)$

$C_4 =14$

The Catalan numbers form the following series: $(1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862...)$

Note: The Catalan numbers readily appear in many interesting counting problems.

• The number of ways to put parentheses around $n$ numbers for multiplication.
• The number of paths to climb up a $2n$ x $2n$ grid without going above the diagonal.
• The number of possible binary trees with $n$ leaf nodes.

Constraints:

• $0 \leq$ n $\leq 22$

Examples