Statement

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

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

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

C4=14C_4 =14

The Catalan numbers form the following series: (1,1,2,5,14,42,132,429,1430,4862...)(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 nn numbers for multiplication.
  • The number of paths to climb up a 2n2n x 2n2n grid without going above the diagonal.
  • The number of possible binary trees with nn leaf nodes.

Constraints:

  • 00 \leq n 22\leq 22

Examples

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.