Find Nth Catalan Number

C_{0} = C_{1} = 1 and C_{n} = \frac{(2 n)!}{((n + 1)! n!)} = \sum_{i = 0}^{n - 1} C_{i} C_{n - 1 - i} = \frac{2 (2 n - 1)}{n + 1} C_{n - 1} for n > 2

Hint

Observe recursive relationship from definition, C(n) is sum of C(i) times C(n - 1 - i) from i = 0 to i < n, create recurisive function calls. The second form of recursive relationship is drived by C(n) / C(n - 1), simplify its equation, then move C(n - 1) to the right.

Python
Javascript

# Python implementation

def C(n):
  if (n <= 1):
    return 1

  result = 0

  for i in range(n):
    result += C(i) * C(n - 1 - i)

  return result

n = 5

print(C(n))

// Javascript implementation

function C(n) {
  if (n <= 1) {
    return 1;
  }

  let result = 0;

  for (let i = 0; i < n; i++) {
    result += C(i) * C(n - 1 - i);
  }

  return result;
}

const n = 5;

console.log(C(n));