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

C Questions

C Questions
C Questions

Note : All the programs are tested under Turbo C/C++ compilers.
It is assumed that,
Programs run under DOS environment, The underlying machine is an x86 system, Program is compiled using Turbo C/C++ compiler.
The program output may depend on the information based on this assumptions (for example sizeof(int) == 2 may be assumed).
Predict the output or error(s) for the following:

void main()
{
int const * p=5; printf("%d",++(*p));
}
Answer:
Compiler error: Cannot modify a constant value.
Explanation:
p is a pointer to a "constant integer". But we tried to change the value of the "constant integer".
main()
{
char s[ ]="man"; int i;
for(i=0;s[ i ];i++)
printf("\n%c%c%c%c",s[ i ],*(s+i),*(i+s),i[s]);
}
Answer: mmmm
aaaa nnnn
Explanation

Zoho Interview | Set 1 (Advanced Programming Round)

Third Round: (Advanced Programming Round) Here they asked us to create a “Railway reservation system” and gave us 4 modules. The modules were:
    1. Booking
    2. Availability checking
    3. Cancellation
    4. Prepare chart
We were asked to create the modules for representing each data first and to continue with the implementation phase.

 My Solution :

#include<stdio.h>#include<conio.h>#include<stdlib.h>#include<string.h>#include<iostream.h>#include<time.h>#include<iomanip.h>#include<fstream.h>char f[10]="f";char s[10]="s";int addr,ad,flag,f1,d,m,i,amt;float tamt; class login {public:char id[100];char pass[100];char*password;void getid(){ cout<<"Enter your id:";gets(id); password=getpass("Enter the password:");strcpy(pass,password);}void displayid(){ cout<<"Id:";puts(id); cout<<"Password:";puts(pass);}}; class detail {public:in…

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