Massive Algorithms: Catalan Number

Related: Combinatorics - Summary
Program for nth Catalan Number | GeeksforGeeks
Catalan numbers are a sequence of natural numbers that occurs in many interesting counting problems like following.
1) Count the number of expressions containing n pairs of parentheses which are correctly matched. For n = 3, possible expressions are ((())), ()(()), ()()(), (())(), (()()).
2) Count the number of possible Binary Search Trees with n keys (See this)
3) 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.

Using Binomial Coefficient

http://www.geeksforgeeks.org/space-and-time-efficient-binomial-coefficient/

C(n, k) = n! / (n-k)! * k!
        = [n * (n-1) *....* 1]  / [ ( (n-k) * (n-k-1) * .... * 1) * 
                                    ( k * (k-1) * .... * 1 ) ]
After simplifying, we get
C(n, k) = [n * (n-1) * .... * (n-k+1)] / [k * (k-1) * .... * 1]

Also, C(n, k) = C(n, n-k)  // we can change r to n-r if r > n-r

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

$C_n = \frac{1}{n+1}{2n\choose n}$

unsigned long int binomialCoeff(unsigned int n, unsigned int k)

{

    unsigned long int res = 1;

    // Since C(n, k) = C(n, n-k)

    if (k > n - k)

        k = n - k;

    // Calculate value of [n*(n-1)*---*(n-k+1)] / [k*(k-1)*---*1]

    for (int i = 0; i < k; ++i)

{

        res *= (n - i);

        res /= (i + 1);

}

    return res;

}

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

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];

}

Recursive Solution
Catalan numbers satisfy the following recursive formula.
$C_0 = 1 \quad \mbox{and} \quad C_{n+1}=\sum_{i=0}^{n}C_i\,C_{n-i}\quad\text{for }n\ge 0;$

We can also use below formula to find nth catalan number in O(n) time.

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

f(n)= f(n-1) + f(n-2)f(1) + f(n-3)f(2) + ... + f(1)f(n-2) + f(n-1)

http://geeksquiz.com/find-number-valid-parentheses-expressions-given-length/
Given a number n find the number of valid parentheses expressions of that length.
This is mainly an application of Catalan Numbers. Total possible valid expressions for input n is n/2’th Catalan Number if n is even and 0 if n is odd.

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

}

// Function to find possible ways to put balanced parenthesis

// in an expression of length n

unsigned long int findWays(unsigned n)

{

    // If n is odd, not possible to create any valid parentheses

    if (n & 1) return 0;

   // Otherwise return n/2'th Catalan Numer

   return catalan(n/2);

}

http://www.cnblogs.com/wuyuegb2312/p/3016878.html

《编程之美》4.3买票找零）：2n个人排队买票，其中n个人持50元，n个人持100元。每张票50元，且一人只买一张票。初始时售票处没有零钱找零。请问这2n个人一共有多少种排队顺序，不至于使售票处找不开钱？

分析1：队伍的序号标为0,1,...,2n-1,并把50元看作左括号，100元看作右括号，合法序列即括号能完成配对的序列。对于一个合法的序列，第0个一定是左括号，它必然与某个右括号配对，记其位置为k。那么从1到k-1、k+1到2n-1也分别是两个合法序列。那么，k必然是奇数（1到k-1一共有偶数个），设k=2i+1。那么剩余括号的合法序列数为f(2i)*f(2n-2i-2)个。取i=0到n-1累加，

并且令f(0)=1，再由组合数C(0,0)=0,可得

http://www.cnblogs.com/wuyuegb2312/p/3016878.html

http://www.geeksforgeeks.org/dyck-path/

Consider a n x n grid with indexes of top left corner as (0, 0). Dyck path is a staircase walk from bottom left, i.e., (n-1, 0) to top right, i.e., (0, n-1) that lies above the diagonal cells (or cells on line from bottom left to top right).

The task is to count the number of Dyck Paths from (n-1, 0) to (0, n-1).

The number of Dyck paths from (n-1, 0) to (0, n-1) can be given by the Catalan numberC(n).

    public static int countDyckPaths(int n)

{

        // Compute value of 2nCn

        int res = 1;

        for (int i = 0; i < n; ++i)

{

            res *= (2*n - i);

            res /= (i + 1);

}

        // return 2nCn/(n+1)

        return res / (n+1);

}

Find number of sequences of 1 and -1 such that every sequence follows below constraints :
a) The length of a sequence is 2n
b) There are equal number of 1’s and -1’s, i.e., n 1’s, n -1s
c) Sum of prefix of every sequence is greater than or equal to 0. For example, 1, -1, 1, -1 and 1, 1, -1, -1 are valid, but -1, -1, 1, 1 is not valid.

Number of paths of length m + n from (m-1, 0) to (0, n-1) that are restricted to east and north steps.

Read full article from Program for nth Catalan Number | GeeksforGeeks

Catalan Number - Summary

Labels

Popular Posts