Catalan Numbers is a well known sequence of integers that appear in combinatorics, there is a chance that you might have run into such counting problems and you might have even solved them with DP without realizing that they are a known sequence. Here is a problem to get us started.

### Binary Trees Count

Find the count of different binary trees with $$$n$$$ nodes, we'll denote to that by $$$C_n$$$. This can be solved by observing the substructure of the problem:

From the root, the left subtree $$$a$$$ can be *any* binary tree of size $$$x$$$, the right subtree $$$b$$$ can be *any* binary tree of size $$$y$$$, such that $$$x+y=n-1$$$ (as we took one node as the root). With the base case at $$$C_0=1$$$ as the empty tree is a valid tree of size $$$0$$$. This directly gives us the answer by the following recurrence relation: (Segner's recurrence relation)

The sequence of numbers $$$C_0, C_1, C_2, ...$$$ is called **Catalan Numbers**, and for reference they are: $$$1, 1, 2, 5, 14, 42, ...$$$.

This gives us a simple $$$O(n^2)$$$ implementation with DP, however can we do better? In fact we can, this simple recurrence formula gives out the same values: