Problem Statement

Given an integer N, find the Nth Catalan number.

Theory

The Catalan numbers are a sequence of natural numbers that can be defined recursively. The Nth Catalan number, denoted as C(N), represents the number of different ways a convex polygon with N+1 sides can be triangulated (non-crossing partitions) and various other combinatorial structures.

The Nth catalan number, Cn can be calculated using the following recursive formula: