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 C3 = 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.
C3 = C0C2 + C1C1+C2C0
C2C0
Below you can see two different BST using C2 and C0, we take below as adding node 3 on 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.
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.
C0C2
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.