“If you know what CATALAN numbers can do ,You are curious about competitive programming.” –A_OLD_MONK
CATALAN numbers are series of amazing numbers which answers your lots of questions with simple implementation (Simple ? it depends how you implement :D).
So before starting about what is the use of CATALAN numbers lets have a look at catalan numbers series…
The first few CATALAN numbers for
n = 0, 1, 2, 3, … are
1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, … and So on .
Application’s:-
Few applications of these numbers are:-
1:-Cn counts the number of expressions containing n pairs of parentheses which are correctly matched:
For n=3 (3-left parenthesis,3-right parenthesis), Cn =5
((())), ()(()), ()()(), (())(), (()())
2:-Cn is the number of different ways (n + 1) factors can be completely parenthesized.
For n=3 Cn =5
((ab)c)d, (a(bc))d , (ab)(cd) , a((bc)d) , a(b(cd))
3:- Count the number of possible Binary Search Trees with n keys
4:-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.
5:-Cn is the number of different ways a convex polygon with (n + 2) sides can be cut into triangles by connecting vertices with straight lines.
6:- Cn is the number of permutations of {1, …, n} that avoid the pattern 123 (or any of the other patterns of length 3); that is, the number of permutations with no three-term increasing subsequence. For n = 3, these permutations are 132, 213, 231, 312 and 321. For n = 4, they are 1432, 2143, 2413, 2431, 3142, 3214, 3241, 3412, 3421, 4132, 4213, 4231, 4312 and 4321.
7:-Cn is the number of ways to tile a stairstep shape of height n with n rectangles. The following figure illustrates the case n = 4:
8:-Cn is the number of ways to form a “mountain ranges” with n upstrokes and n down-strokes that all stay above the original line.The mountain range interpretation is that the mountains will never go below the horizontal.
9:-Cn is the number of ways that the vertices of a convex 2n-gon can be paired so that the line segments joining paired vertices do not intersect. This is precisely the condition that guarantees that the paired edges can be identified (sewn together) to form a closed surface of genus zero (a topological 2-sphere).
How to find the nth CATALAN Number?
Method 1:-
The recursive definition:-
Time Complexity:-
i.e. exponential approx. 
Note:- We can use Dynamic Programming(DP) to reduce the complexity from exponential(as above) to O(n2).
Using, catalan[i] += catalan[j] * catalan[i-j-1];
Method 2:-
Using Binomial Coefficient :-
Implementation In C Using Method 2:-
#include<stdio.h>
unsigned long int binomial(unsigned int n, unsigned int k)
{
unsigned long int res = 1;
if (k > n - k)
k = n - k;
for (int i = 0; i < k; ++i)
{
res *= (n - i);
res /= (i + 1);
}
return res;
}
unsigned long int catalan(unsigned int n)
{
unsigned long int c = binomialCoeff(2*n, n);
return c/(n+1);
}
int main()
{
for (int i = 0; i < 10; i++)
printf("%d",catalan(i));
return 0;
}
Time Complexity:- O(n).
Note:– If facing problem in implementing any other method ,Please feel free to ask 🙂 .
For more detail click Catalan Numbers
Anonymous Coders 