Nth Catalan Number

Difficulty Level Medium
Frequently asked in Amazon
Dynamic Programming MathViews 2587

In the Nth Catalan number problem, we have given an integer n. Find the first n Catalan numbers. Catalan numbers are a series of positive integers which is seen in many counting problems.

They are used to count –

  • BSTs (Binary search trees) with n keys.
  • Certain types of lattice paths.
  • Permutations

and many more such problems. The recursive formula for Catalan numbers is –

C0 = 0 and Cn+1 = Σ Ci Cn-i for n>=0 and n=>i>=0.

The first few numbers of Catalan number series – 1, 1, 2, 5, 14…… for n = 0, 1, 2, 3, 4…… respectively. 

Example

Input : n=2

Output : 1 1

Input : n=9

Output : 1 1 2 5 14 42 132 429 1430

Recursive Method for Nth catalon number

Algorithm

  1. Initialise a variable n.
  2. Base case – if n is less than equal to 1 return 1.
  3. Recursive case – return sum of all cat (i) x cat (n-i-1) for all i between 0 and n (0 inclusive).

Time Complexity: O(3n)

Space Complexity: O(1)

Implementation for Nth catalon number

C++ Program

#include<bits/stdc++.h> 
using namespace std; 
  
long int cat(int n){ 
    // Base case 
    if(n<=1) 
        return 1; 
  
    // cat(n)= sum of cat(i)*cat(n-i-1) 
    long int r = 0; 
    for (int i=0; i<n; i++) 
        r += cat(i)*cat(n-i-1); 
    return r; 
} 
  
int main(){
    int n=3;
    for (int i=0; i<n; i++) 
        cout<<cat(i)<< " "; 
    return 0; 
}
1 1 2

Java Program

class Catalan{ 
    int cat(int n) { 
        int r = 0; 
          
        // Base case 
        if(n<=1) { 
            return 1; 
        } 
        // cat(n)= sum of cat(i)*cat(n-i-1)
        for(int i=0; i<n; i++) { 
            r+=cat(i)*cat(n-i-1); 
        } 
        return r; 
    } 
  
    public static void main(String[] args) { 
        Catalan c = new Catalan(); 
        int n=3;
        for (int i=0; i<n; i++) { 
            System.out.print(c.cat(i) + " "); 
        } 
    } 
}
1 1 2

Dynamic Programming Method for Nth Catalan numbers

Algorithm

  1. Initialize a variable n and an array c to store Catalan numbers.
  2. Initialize the first two elements of the array as 1 and 1 respectively.
  3. Traverse all the values till n starting from 2 one by one and update the array values as the sum of c[ j ] * c[ i-j-1 ].
  4. Return c[n].

Time Complexity: O(n2)

Space Complexity: O(n)

Implementation for Nth catalon number

C++ Program

#include<bits/stdc++.h>
using namespace std;

long int cat(int n){ 
    
    long int c[n+1]; 
  
    // Initialisation of first two values 
    c[0]=1;
    c[1]=1; 
  
    for(int i=2; i<=n; i++){ 
        c[i] = 0; 
        for(int j=0; j<i; j++) 
            c[i] += c[j] * c[i-j-1]; 
    } 
  
    // Return last number in array
    return c[n]; 
} 
  
int main(){ 
    int n=3;
    for(int i=0; i<n; i++) 
        cout << cat(i) << " "; 
    return 0; 
}
1 1 2

Java Program

class Catalan{ 
  
    static int cat(int n){ 
        int c[] = new int[n + 2]; 
  
         // Initialisation of first two values 
        c[0]=1;
        c[1]=1; 
      
        for(int i=2; i<=n; i++){ 
            c[i] = 0; 
            for(int j=0; j<i; j++) 
                c[i] += c[j] * c[i-j-1]; 
        } 
      
        // Return last number in array
        return c[n]; 
    } 
    public static void main(String[] args) { 
        int n=3;
        for(int i=0; i<n; i++){ 
            System.out.print(cat(i) + " "); 
        } 
    } 
}
1 1 2

Using the Binomial Coefficient

Here we will directly use the formula to find the nth Catalan number i.e.

Cn = ( ( 2n! ) / ( (n+1)! n! ) )

Time Complexity: O(n)

Space Complexity: O(1)

Implementation for Nth Catalan numbers

C++ Program

#include<bits/stdc++.h>
using namespace std;

long int biCoef(int n, int m){ 
    long int r=1; 
  
    if(m>(n-m)) 
        m=n-m; 

    for (int i=0; i<m; ++i){ 
        r *= (n-i); 
        r /= (i+1); 
    } 
  
    return r; 
} 

long int cat(int n){ 
    // Calculate value of 2nCn 
    long int c = biCoef(2*n, n); 
  
    // return 2nCn/(n+1) 
    return c/(n+1); 
} 
int main(){
    int n=3;
    for (int i=0; i<n; i++) 
        cout << cat(i) << " "; 
    return 0; 
}
1 1 2

Java Program

class Catalan{ 
  
    static long biCoef(int n, int m){ 
        long r=1; 
      
        if(m>(n-m)) 
            m=n-m; 
    
        for (int i=0; i<m; ++i){ 
            r *= (n-i); 
            r /= (i+1); 
        } 
      
        return r; 
    } 
    
    static long cat(int n){ 
        // Calculate value of 2nCn 
        long c = biCoef(2*n, n); 
      
        // return 2nCn/(n+1) 
        return c/(n+1); 
    } 
    public static void main(String[] args) { 
        int n=3;
        for(int i=0; i<n; i++){ 
            System.out.print(cat(i) + " "); 
        } 
    } 
}
1 1 2

References

Translate »