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.
Table of Contents
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
- Initialise a variable n.
- Base case – if n is less than equal to 1 return 1.
- 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
- Initialize a variable n and an array c to store Catalan numbers.
- Initialize the first two elements of the array as 1 and 1 respectively.
- 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 ].
- 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