Skip to main content

Catalan number



Catalan number is given directly in terms of binomial coefficients by


C_n = \frac{1}{n+1}{2n\choose n} = \frac{(2n)!}{(n+1)!\,n!} = \prod\limits_{k=2}^{n}\frac{n+k}{k} \qquad\mbox{ for }n\ge 0.


The first Catalan numbers for n = 0, 1, 2, 3, … are
1, 1, 251442132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324

Applications in combinatorics


1. Cn 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:
N(n,k) = \frac{1}{n}{n\choose k}{n\choose k-1}.

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)) 

 4. Cn is the number of full binary trees with n + 1 leaves: 

Number of full binary trees

5. Cn is the number of non-isomorphic ordered trees with n vertices. (An ordered tree is a rooted tree in which the children of each vertex are given a fixed left-to-right order.)


6. Cn is the number of monotonic lattice paths along the edges of a grid with n × n square cells

The following diagrams show the case n = 4:


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. 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(a form of Polygon triangulation). The following hexagons illustrate the case n = 4:


8. Cn is the number of stack-sortable permutations of {1, ..., n}. A permutation w is called stack-sortable if S(w) = (1, ..., n) (  also called a tree permutation )

9. Cn 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.

10. Cn is the number of noncrossing partitions

.
11. 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:



12. Cn 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. 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 horizon.


14. 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.

15. Cn is the number of semiorders on n unlabeled items


Recursive Solution
Catalan numbers satisfy the following recursive formula.
catalan

// 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;
}

Using Binomial Coefficient 
We can also use the below formula to find nth catalan number in O(n) time.
catalan3

// 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[i-j-1];
    }
    // Return last entry
    return catalan[n];
}

Comments

Popular posts from this blog

ORACLE 9i practice solutions

Created by BCL easyConverter SDK 3 (HTML Version)

Hackerrank > SQL > Basic Select

Select
01-Select All
Given a City table, whose fields are described as +-------------+----------+ | Field       | Type     | +-------------+----------+ | ID          | int(11)  | | Name        | char(35) | | CountryCode | char(3)  | | District    | char(20) | | Population  | int(11)  | +-------------+----------+
write a query that will fetch all columns for every row in the table.

My Solution
SELECT*FROM city;
---------------------------------------------------------------------------------
02-Select by ID
Given a City table, whose fields are described as

Zoho Puzzle Questions With Answers

Measuring Time Logic Puzzle You are given with two ropes with variable width. However if we start burning both the ropes, they will burn at exactly same time i.e. an hour. The ropes are non-homogeneous in nature. You are asked to measure 45 minutes by using these two ropes.

How can you do it?

Please note that you can’t break the rope in half as it is being clearly stated that the ropes are non-homogeneous in nature.
Answer & Explanation Solution: 45 minutes

Explanation :
All you have to do is burn the first rope from both the ends and the second rope from one end only simultaneously. The first rope will burn in 30 minutes (half of an hour since we burned from both sides) while the other rope would have burnt half. At this moment, light the second rope from the other end as well. Where, the second rope would have taken half an hour more to burn completely, it will take just 15 minutes as we have lit it from the other end too.

Thus you have successfully calculated 30+15 = 45 minutes …