Catalan Number

Software Development
#1

Catalan numbers are a sequence of natural numbers that occurs in many interesting counting problems like following.

  1. Count the number of expressions containing n pairs of parentheses which are correctly matched. For n = 3, possible expressions are ((())), ()(()), ()()(), (())(), (()()).
  2. Count the number of possible Binary Search Trees with n keys.
  3. Count 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.
  4. Given a number n, return the number of ways you can draw n chords in a circle with 2 x n points such that no 2 chords intersect.

Recursive Solution
Catalan numbers satisfy the following recursive formula.

Following is the implementation of above recursive formula.

#include <iostream>

using namespace std;

// A recursive function to find nth catalan number

unsigned long int catalan(unsigned int n)

{

`` // Base case

`` if (n <= 1)

`` return 1;

`` // catalan(n) is sum of

`` // catalan(i)*catalan(n-i-1)

`` unsigned long int res = 0;

`` for ( int i = 0; i < n; i++)

`` res += catalan(i)

`` * catalan(n - i - 1);

`` return res;

}

// Driver code

int main()

{

`` for ( int i = 0; i < 10; i++)

`` cout << catalan(i) << " " ;

`` return 0;

}

Output

1 1 2 5 14 42 132 429 1430 4862

Time complexity of above implementation is equivalent to nth catalan number.

The value of nth catalan number is exponential that makes the time complexity exponential.

Dynamic Programming Solution : We can observe that the above recursive implementation does a lot of repeated work (we can the same by drawing recursion tree). Since there are overlapping subproblems, we can use dynamic programming for this. Following is a Dynamic programming based implementation .

#include <iostream>

using namespace std;

// A dynamic programming based function to find nth

// Catalan number

unsigned long int catalanDP(unsigned int n)

{

`` // Table to store results of subproblems

`` unsigned long int catalan[n + 1];

`` // Initialize first two values in table

`` catalan[0] = catalan[1] = 1;

`` // Fill entries in catalan[] using recursive formula

`` for ( int i = 2; i <= n; i++) {

`` catalan[i] = 0;

`` for ( int j = 0; j < i; j++)

`` catalan[i] += catalan[j] * catalan[i - j - 1];

`` }

`` // Return last entry

`` return catalan[n];

}

// Driver code

int main()

{

`` for ( int i = 0; i < 10; i++)

`` cout << catalanDP(i) << " " ;

`` return 0;

}

Output

1 1 2 5 14 42 132 429 1430 4862

Time Complexity: Time complexity of above implementation is O(n2)