Challenge: The Catalan Numbers

Problem statement

The 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$

You can already see the hefty amount of recursion in this series.

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

Applications of the Catalan numbers

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. This has been shown in the visualization below.