Catalan Numbers

dhruv sharma
Last Updated: May 13, 2022

Introduction

If you have been a competitive programmer or someone working on preparing for your campus placements or technical interviews, you probably must have come across the following question:

Suppose you have 'n' pairs of parentheses and you would like to form valid groupings of them, here, "valid" means that each open parenthesis has a matching closing parenthesis. For example, "(()())" is valid, but "())()(" is not then, how many groupings are there for each value of n?

If not, does the name Catalan’s number sound familiar?

 

It's alright if you're hearing this name for the first time.

You may be wondering what it is and why we need to solve the problem using Catalan numbers. This article will explain what Catalans numbers are and how to use them.

Before delving deeper into the concept, we must first understand what Catalan numbers are.

Problems where we need Catalan numbers

Catalan numbers are a sequence of numbers named after the Belgian mathematician Catalan, who lived in the 19th century. (In fact, it was known before to Euler, who lived a century before Catalan).

The first few numbers Catalan numbers, Cn (where Cn represents the nth catalan numbers (starting from zero):

1,1,2,5,14,42,132,429,1430,…

It has many applications in combinatorial and counting problems where the Catalan number (Cn) is often the required solution.

A few examples of such problems are:

  1. Finding all Diagonal Avoiding Paths: The number of mono-tonic lattice paths from point (0,0) to point (n,n) in a square lattice of size n×n, which do not pass above the main diagonal (i.e. connecting (0,0) to (n,n)).
     

 

Image Source - link

Examples of such valid paths that do not cross the diagonals

 

  1. Count rooted Binary Trees with ‘N’ internal nodes: The number of non-isomorphic full binary trees with 'n' internal nodes (i.e. nodes having at least one son).

 

Multiple rooted binary trees with ‘N’ internal node

 

  1. Balanced Parentheses: Number of correct bracket sequences consisting of n opening and n closing brackets. 

 

Image Source - link

 

Recursive implementation of Catalan Number generation

One can easily deduce the recurrence formula from the problem of the correct bracket sequence.

 


The required implementation of the above recursive formula is as follows:

# A recursive function to

# find nth Catalan number recursively

def nthCatalanNumber(n):

# Base Case

if n <= 1:

return 1

 

# Catalan(n) is the summation of

# nthcatalan(i) * nthcatalan(n-i-1)

cat = 0

for i in range(n):

cat += nthCatalanNumber(i) * nthCatalanNumber(n-i-1)

 

return cat

 

# Main

for i in range(10):

print(nthCatalanNumber(i)),

 

 

Output:

1 1 2 5 14 42 132 429 1430 4862

 

This method is straightforward, but we do not use it commonly. Wondering why?

That is because it has exponential time complexity.
 

 

As we know, while writing any program, Time and Space Complexity plays a vital role in choosing the algorithm. Therefore we should look for a different approach for generating such Catalan numbers.

Catalan Number generation using Dynamic Programming

Since it is clear that the recursive approach has exponential time complexity, we know that it does a lot of repeated work (we can do the same by drawing a recursion tree); since there are overlapping subproblems, we can use dynamic programming for the same.

The following is Dynamic programming based implementation :

# Dynamic programming based approach to find the nth Catalan number

 

def nthCatalanNumber(n):

if (n == 0 or n == 1):

return 1

 

# Table to store results of subproblems

catalanNumbers = [0] * (n+1)

 

# Initialize first two values in table

catalanNumbers[0] = 1

catalanNumbers[1] = 1

 

# Fill entries in catalanNumbers[] using recursive formula

for i in range(2, n + 1):

for j in range(i):

catalanNumbers[i] += catalanNumbers[j]* catalanNumbers[i-j-1]

 

# Return last entry

return catalanNumbers[n]

 

# Main

for i in range(10):

print(nthCatalanNumber(i), end=" ")

 

 

Output:

1 1 2 5 14 42 132 429 1430 4862 

 

Time Complexity: O(N^2)

Space Complexity: O(N)

We can see that the time complexity of the dynamic programming approach is less than that of the recursive method when it comes to solving the same problem.

Catalan Number generation using Binomial Coefficient

To further reduce the time complexity and efficiently calculate Catalan's numbers, we can also use binomial coefficient formulas to find the nth Catalan number in O(n) time ( as discussed in one of the approaches of our problems on codestudio - link ).


(here, (NK) denotes the usual binomial coefficient, i.e. number of ways to select k objects from a set of n objects).

The code given below uses Kadane’s algorithm to find the maximum contiguous subarray sum in such a case.

# Finding nth Catalan Number in O(N) time.

 

# Returns value of Binomial Coefficient C(n, k).

def binomialCoefficient(n, k):

 

# since C(n, k) = C(n, n - k)

if (k > n - k):

k = n - k

 

# initialize result

res = 1

 

# Calculate value of 

     # [n * (n-1) *---* (n-k + 1)] / [k * (k-1) *----* 1]

for i in range(k):

res = res * (n - i)

res = res / (i + 1)

return res

 

def nthCatalanNumber(n):

c = binomialCoefficient(2*n, n)

return c/(n + 1)

 

# Main

for i in range(10):

print(nthCatalanNumber(i), end=" ")

 

 

Output:

1 1 2 5 14 42 132 429 1430 4862 

 

Time Complexity: O(N)

Space Complexity: O(1)

 

We recommend you to practice the binomial coefficient problem on Codestudio after knowing all about its approach.

Applications of Catalan numbers:

The different set of problems that can be shown/reduced to be completely equivalent to a problem which has their solutions which is essentially the same as the Catalan number sequence that we learnt about are as follows:

1. Counting the Mountain Ranges: Number of ways to form "mountain ranges" with n upstrokes and n down-strokes so that they all stay above the original line. The mountain range interpretation or a supposition is that the mountains will never go below the horizon, and in this case, we consider a single mountain range with zero strokes.

 

Image Source - link

 

2. Counting Polygon triangulations: Counting the Number of ways one can split a convex polygon of n+2 sides into triangles by connecting vertices, i.e., counting the number of ways to triangulate a regular polygon with n + 2 sides, the solution will also exist as Catalan numbers.


Image Source - link

 

3. Counting the number of Multiplication Orderings: Suppose you have a set of n + 1 numbers to multiply together with n multiplications to perform. Without changing the order of numbers themselves, one can multiply the numbers together in different orders. Here are the possible multiplication orderings for 0 ≤ n ≤ 4 multiplications. 

 

Image Source - link 

Frequently Asked Questions

1. What are Catalan Numbers?
Catalan numbers is a number sequence, which is found helpful in counting and several combinatorial problems, often involving recursively defined objects.
 

2. What are different strategies to generate Catalan Numbers?
Yes, the Catalan numbers can be generated using a recursive, dynamic and binomial coefficient approach.

 

3. What is the time complexity of generating Nth Catalan numbers using the dynamic programming approach?
The dynamic programming approach uses optimal sub-structures and reduces the unnecessary repetitive work done while generating Catalan numbers using the recursive method. Therefore the dynamic programming approach reduces the time complexity from exponential order (as obtained in recursive approach) to O(N^2).

 

4. What are some applications of Catalan numbers?
Some of the problems the solutions of which are equivalent to the Catalan numbers sequence are:

  • Counting mountain ranges
  • Counting diagonal avoiding paths
  • Counting rooted binary trees with N internal nodes
  • Counting groupings from a valid ‘N’ pairs of parenthesis 

 

5. What is the binomial formula for generating Catalan Numbers?
The binomial formula for generating Catalan numbers is as follows:

Key Takeaways

This article explains Catalan Numbers and how we can leverage them to solve common problems in technical interviews. 

We also saw that there's no need to collect loads of redundant and additional steps while we are working on strategies to generate Catalan numbers. We can optimise the answer by collecting only the information we need to know using the dynamic programming approach.

We also looked at problems whose solution is the same Catalan numbers sequence that we generated.

Apart from that, it would be best if you learned more about other top Standard Algorithms for a Coding Interview.

Additionally, you can use CodeStudio to practise a wide range of DSA tasks typically asked in interview rounds. This will assist you in mastering efficient coding methodologies, with the added benefit of scholar interview experiences in large product-based organisations.

Happy learning!

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think