Nikhil Kumar SinghVrishchik

**Catalan numbers** are a sequence of numbers involving recursion-based problems, mainly found in counting problems.

In this article, we will try to prove the Catalan numbers using one of its applications for **possible numbers of rooted binary search trees with n+1 nodes. A rooted binary tree has either two or zero children.**

Here **n = 3** nodes in the tree, so according to the Catalan number, we can see that C_{3} = 5, let’s see how we can do this graphically.

Now to calculate for n = 3, we will go through each component in the equation and try to decide the logic behind our terms.

C_{3} = C_{0}C_{2} + C_{1}C_{1}+C_{2}C_{0}

C_{2}C_{0}

Below you can see two different BST using C_{2} and C_{0}, we take below as adding node 3 on to the right of the subtree. Here you can see the structure of C_{2} is maintained, only node 3 is added such that it satisfies the BST property.

Below you can see two different BST using C1 twice, we take below as adding the node 3 in the middle. Here you can see the structure of C1 is maintained, only node 3 is added such that it satisfies the BST property.

C_{0}C_{2}

Below you can see two different BST using C0 and C2, which we take below as adding node 3 to the right of the subtree. Here you can see the structure of C2 is maintained only node 3 is added such that it satisfies the BST property.

We can calculate Catalan numbers using two different methods: Recursive and analytical.

**Using Dynamic Programming Solution:** As we can see in the above recurrence, there is a lot of repeated work. Since there is overlapping of subproblems we use dynamic programming to store those subproblems. Below is the code for that.

```
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
```

```
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
ll catDP(ll n) {
ll cat[n + 1];
cat[0] = cat[1] = 1;
for (int i = 2; i <= n; i++) {
cat[i] = 0;
for (int j = 0; j < i; j++)
cat[i] += cat[j] * cat[i - j - 1];
}
return cat[n];
}
int main() {
ll n;
cin >> n;
cout << catDP(n);
return 0;
}
```

**Input:**`10`

**Output:**`16796`

**Time complexity:** As we can see above there are two nested loops, therefore the time complexity for our code is O(n2).

Space complexity: Here we are using an extra array to store the Catalan value from 0 to n, therefore O(n) space complexity.

**Using Binomial Coefficient:** We can see that the DP approach takes extra space as well as costs O(n2) time. Using the binomial coefficient approach we can reduce it to O(1) space and O(n) time complexity.

```
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
```

```
#include <iostream>
using namespace std;
#define ll long long int
ll binomialCoff(ll n, ll k) {
ll res = 1;
if (k > n - k)
k = n - k;
for (int i = 0; i < k; ++i) {
res *= (n - i);
res /= (i + 1);
}
return res;
}
ll cat(ll n) {
ll c = binomialCoff(2 * n, n);
return c / (n + 1);
}
int main() {
ll n;
cin >> n;
cout << cat(n);
return 0;
}
```

**Input:**`10`

**Output:**`16796`

**Time complexity:** This has a linear time complexity, i.e, **O(n).**

**Space complexity:** We have only used variables so no extra space is **O(1).**

**Applications of Catalan number in some problems:**

A possible number of rooted binary search trees with

**n+1**nodes. A rooted binary tree has either two or zero children.Number of ways to cover the ladder using

**N**rectangles.Parenthesis or bracket combination, correct bracket sequence consisting of N opening/closing brackets.

Possible number of ways to reach from one to other ends of a matrix.

Number of ways to connect

**2N**points on a circle to form**N**disjoint chords.

Ways to parenthesize **N+1** factors.

Discuss this article in the forums
Recursion is a wonderful programming tool. It provides a simple, powerful...

Read More Discuss this article in the forums
Introduction
Counting the objects that satisfy some criteria is a very comm...

Read More Discuss this article in the forums.
Introduction
Straight-forward problems that don’t require a special tech...

Read More