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.
Dynamic Programming Solution
Recursive Solution
Catalan numbers satisfy the following recursive formula.
.
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.
http://www.cnblogs.com/wuyuegb2312/p/3016878.html
http://www.cnblogs.com/wuyuegb2312/p/3016878.html
http://www.geeksforgeeks.org/dyck-path/
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.
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);}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.
We can also use below formula to find nth catalan number in O(n) time.
.
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 nunsigned 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);}
《编程之美》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.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.
.
