Challenge: The Catalan Numbers

In this lesson, you will solve your first coding challenge using bottom-up dynamic programming.

Problem statement

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

C0=1C_0 = 1

Cn=i=0n1CiCn1iC_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 nthn^{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.

C4C_4 for example would be equal to:

C4=C0C3+C1C2+C2C1+C3C0C_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.

Get hands-on with 1200+ tech skills courses.