Catalan Numbers
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:
 Finding all Diagonal Avoiding Paths: The number of monotonic 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
 Count rooted Binary Trees with ‘N’ internal nodes: The number of nonisomorphic full binary trees with 'n' internal nodes (i.e. nodes having at least one son).
Multiple rooted binary trees with ‘N’ internal node
 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(ni1) cat = 0 for i in range(n): cat += nthCatalanNumber(i) * nthCatalanNumber(ni1)
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[ij1]
# 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 * (n1) ** (nk + 1)] / [k * (k1) ** 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 downstrokes 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 substructures 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 productbased organisations.
Happy learning!
Comments
No comments yet
Be the first to share what you think