# Nth Catalan Number

Difficulty Level Medium
Dynamic Programming MathViews 1150

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 »