Program for Nth Catalan Number

Catalan numbers (C_n) 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 (C_n) in counting problems

1. C_n 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
2. C_n is the count of number of expressions containing n pairs of parentheses which are correctly matched:
   ((()))     ()(())     ()()()     (())()     (()())
3. C_n is the number of ways to form a “mountain range” with n upstrokes and n downstrokes that all stay above a horizontal line.
4. C_n is the number of possible Binary Search Trees with n keys.
5. C_n 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.
6. 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 could find more applications here: Catalan number – Wikipedia

Recursive Approach to calculate Nth Catalan Number

Let’s calculate the value of Catalan number (C_n) by using the recurrence relation:

C_n+1 = \sum_{i=0}^{n} C_{i}C_{n-i} for n >= 0
where, C₀ = 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(3ⁿ)

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 could 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(n²)
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 could 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)