Catalan Number and Its Application

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₃ = 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₃ = C₀C₂ + C₁C₁+C₂C₀

C₂C₀
Below you can see two different BST using C₂ and C₀, we take below as adding node 3 on to the right of the subtree. Here you can see the structure of C₂ 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₀C₂
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.

Calculating Catalan Numbers

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

Recursive

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.

Analytical

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.