Catalan number is given directly in terms of binomial coefficients by
The first 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
Applications in combinatorics
 1. C_{n} is the number of Dyck words
 For example, the following are the Dyck words of length 6:
 XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY.

 2. Pairs of parentheses which are correctly matched: (using Narayana numbers)
 ((())) ()(()) ()()() (())() (()())
 The Narayana numbers can be expressed in terms of binomial coefficients:
 3. The number of ways of associating n applications of a binary operator). For n = 3, for example, we have the following five different parenthesizations of four factors:
 ((ab)c)d (a(bc))d (ab)(cd) a((bc)d) a(b(cd))
 Number of full binary trees
 5. C_{n} is the number of nonisomorphic ordered trees with n vertices. (An ordered tree is a rooted tree in which the children of each vertex are given a fixed lefttoright order.)


 This can be succinctly represented by listing the Catalan elements by column height:^{[5]}[0,0,0,0][0,0,0,1][0,0,0,2][0,0,1,1][0,1,1,1] [0,0,1,2] [0,0,0,3] [0,1,1,2][0,0,2,2][0,0,1,3][0,0,2,3][0,1,1,3] [0,1,2,2][0,1,2,3]
 7. C_{n} is the number of different ways a convex polygon with n + 2 sides can be cut into triangles by connecting vertices with straight lines(a form of Polygon triangulation). The following hexagons illustrate the case n = 4:

 8. C_{n} is the number of stacksortable permutations of {1, ..., n}. A permutation w is called stacksortable if S(w) = (1, ..., n) ( also called a tree permutation )
 9. C_{n} is the number of permutations of {1, ..., n}
 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.

 .
 11. C_{n} is the number of ways to tile a stairstep shape of height n with n rectangles.
 The following figure illustrates the case n = 4:

 12. C_{n} is the number of rooted binary trees with n internal nodes (n + 1 leaves). Illustrated in following Figure are the trees corresponding to n = 0,1,2 and 3. There are 1, 1, 2, and 5 respectively. Here, we consider as binary trees those in which each node has zero or two children, and the internal nodes are those that have children.

 13. C_{n} is the number of ways to form a “mountain ranges” with n upstrokes and n downstrokes that all stay above the original line.The mountain range interpretation is that the mountains will never go below the horizon.

 14. C_{n} is the number of ways that the vertices of a convex 2ngon can be paired so that the line segments joining paired vertices do not intersect.

 Recursive SolutionCatalan numbers satisfy the following recursive formula.
// 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(ni1)
unsigned
long
int
res = 0;
for
(
int
i=0; i<n; i++)
res += catalan(i)*catalan(ni1);
return
res;
}
 Using Binomial CoefficientWe can also use the below formula to find nth catalan number in O(n) time.
// A Binomial coefficient based function to find nth catalan
// number in O(n) time
unsigned
long
int
catalan(unsigned
int
n)
{
// Calculate value of 2nCn
unsigned
long
int
c = binomialCoeff(2*n, n);
// return 2nCn/(n+1)
return
c/(n+1);
}
 Dynamic Programming Solution
// 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[ij1];
}
// Return last entry
return
catalan[n];
}
Comments
Post a Comment