Catalan numbers (Cn) are a sequence of natural numbers that occur in various counting problems. They are named after the French-Belgian mathematician Eugène Charles Catalan (1814–1894).
The first few Catalan numbers are 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786…
The nth Catalan number can be expressed as:
\frac{1}{(n+1)} \binom{2n}{n}
Applications of Catalan Number (Cn) in counting problems
- Cn is the number of Dyck words of length 2n. A Dyck word is a string consisting of n X’s and n Y’s such that no initial segment of the string has more Y’s than X’s.
For example, the following are the Dyck words of length 6:
XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY - Cn is the count of number of expressions containing n pairs of parentheses which are correctly matched:
((())) ()(()) ()()() (())() (()()) - Cn is the number of ways to form a “mountain range” with n upstrokes and n downstrokes that all stay above a horizontal line.
- Cn is the number of possible Binary Search Trees with n keys.
- Cn is the number of full binary trees (A rooted binary tree is full if every vertex has either two children or no children) with n+1 leaves.
- The number of paths with 2n steps on a rectangular grid from bottom left, i.e., (n-1, 0) to top right (0, n-1) that do not cross above the main diagonal.
You can find more applications here: Catalan number – Wikipedia
Recursive Approach to calculate Nth Catalan Number
Let’s calculate the value of Catalan number (Cn) by using the recurrence relation:
Cn+1 = \sum_{i=0}^{n} C_{i}C_{n-i} for n >= 0
where, C0 = 1
Optimal Substructure
Cn+1 = C0Cn + C1Cn-1 + C2Cn-2 + ... + CnC0 Also, C0 = 1 and C1 = 1
Recursive Code
//
// main.cpp
// Catalan Number (Recursive)
//
// Created by Himanshu on 02/04/22.
//
#include <iostream>
using namespace std;
typedef long long ll;
// Calculate Cn
ll calculateCatalanNum (ll n) {
ll ans = 0;
// Base Cases
if (n <= 1) {
return 1;
}
for (ll i=0; i<n; i++) {
ans += (calculateCatalanNum(i) * calculateCatalanNum(n - 1 - i));
}
return ans;
}
int main () {
ll n = 10;
cout<<n<<"th"<<" Catalan number is "<<calculateCatalanNum(n)<<endl;
return 0;
}
Output
10th Catalan number is 16796
Time complexity: O(3n)
Understanding the problem in this approach
Here, certain subproblems are recomputed. Recomputations can be avoided by exploiting optimal substructure and using a Dynamic Programming solution.
Dynamic Programming Approach
We can create an array, C[n+1] in bottom up manner, such that
C[i] += C[j] * C[i-j-1], for 0 <= j < i where, C[0] = C[1] = 1
Code Implementation (Dynamic Programming Approach)
//
// main.cpp
// Catalan Number (Dynamic Programming)
//
// Created by Himanshu on 02/04/22.
//
#include <iostream>
using namespace std;
typedef long long ll;
// Calculate Cn
ll calculateCatalanNum (ll n) {
ll *C = new ll[n+1]();
// Base Cases
C[0] = C[1] = 1;
for (int i=2; i<=n; i++) {
for (int j=0; j<i; j++) {
C[i] += C[j] * C[i - j - 1];
}
}
return C[n];
}
int main() {
ll n = 10;
cout<<n<<"th"<<" Catalan number is "<<calculateCatalanNum(n)<<endl;
return 0;
}
Output
10th Catalan number is 16796
Time complexity: O(n2)
Space complexity: O(n)
Also read:
Optimal space and time complexity approach
In the above post, we’ve computed \binom{n}{r} in O(r) time complexity. We can use the same method to calculate Nth Catalan number which is nothing but, \frac{1}{(n+1)} \binom{2n}{n} ie.
\frac{1}{(n+1)} * \binom{2n}{n} = \frac{1}{(n+1)} * \frac{2n!}{(n!)(n!)}
Code Implementation
//
// main.cpp
// Catalan Number (Efficient)
//
// Created by Himanshu on 02/04/22.
//
#include <iostream>
using namespace std;
typedef long long ll;
// Calculate Binomial Coefficient C(n, r)
ll calculateBinomialCoeff (ll n, ll r) {
ll binomialCoeff = 1;
if (n < r) {
return -1;
}
r = min(r, n-r);
for (ll i=n; i>n-r; i--) {
binomialCoeff = binomialCoeff*i;
binomialCoeff = binomialCoeff/(n-i+1);
}
return binomialCoeff;
}
// Calculate Cn
ll calculateCatalanNum (ll n) {
ll catalanNum = 1;
for (ll i=2*n; i>n; i--) {
catalanNum = catalanNum*i;
catalanNum = catalanNum/(2*n-i+1);
}
return catalanNum/(n+1);
}
int main() {
ll n = 10;
cout<<n<<"th"<<" Catalan number is "<<calculateCatalanNum(n)<<endl;
cout<<n<<"th"<<" Catalan number using Binomial Coefficient (2nCn) is "
<<(calculateBinomialCoeff(2*n, n)/(n+1))<<endl;
return 0;
}
Output
10th Catalan number is 16796 10th Catalan number using Binomial Coefficient (2nCn) is 16796
Time complexity: O(n)
Space complexity: O(1)
One thought on “Program for Nth Catalan Number”