Catalan Number

Definition

Catalan number is a group of numbers that satisfy a specific recurrence relationship. If we use C_k to represent the kth catalan number, then it follows the recurrence relationship below:

C_k = C₁C_k-1 + C₂C_k-2 + … + C_k-1C₁

C₀ = 1, C₁ = 1

Another equivalent form of recurrence formula is:

C_k = C_k-1(4n-2)/(n+1)

The solution is:
C_k = C_2nⁿ/(n+1) = C_2nⁿ - C_2nⁿ⁺¹

Application

Parenthesesation

Parenthesesation means to add parentheses into a equation of matrix product like B = A₁ A₂…A_n and calculate how many different ways there are to add parentheses.
The problem can be divided into sub-problems considering parenthesation of first k matrix and n-k matrix left. So obviously, the total number of parenthesation approaches is catalan number according to the recurrence relationship.

Stack Push and Pop

If there is a stack that is big enough and the pushing sequence is 1,2,3…,n, then how many different poping sequences will appear?

Solution 1

Assume that the last poped number is k, then it means before k is pushed into the stack, numbers that are less than k must have been poped. As a result, the problem is naturaly divided into two sub-problems: poping sequence of 1,…,k-1 and poping sequence of k-1,…,n. Obviously, the total number of poping sequences is catalan number.

Solution 2

This probelm can also be regarded as a problem of permutation and combination. The problem consists n push operation adn n pop operation. So basically, we are arranging the 2n operations among 2n positions.
The total number of ways of arrangement is C_2nⁿ but there are invalid conditions. How to calculate invalid conditions? There are two basic facts:

• When positions of n push operations are selected, the positions and sequence of n pop operations are also determined. There is no second condition. For example, if first n positions are all push operation, then last n position can only be pop n, pop n-1, pop n-2…, pop 1.
• The valid sequence has to be the sequence follows the rules below:
  • For first 2m+1 operations, number of push operations must be no less than that of pop operations. Otherwise, it is obviously invalid since an empty stack cannot pop.

Based on the facts above, we can calcualte invalid conditions like this:
Assume that first 2m+1 operations have s push and 2m+1-s pop. Then remaining operations must be n-s push and n-2m-1+s pop. There must be one m that satisfy that s = m. In this situation, the operations consists (m push, m+1 pop) and (n-m push, n-m-1 pop). From the aspect of permutation, it is equivalent to arrange n-1 pop and n+1 push together.
So the total number of invalid situation is C_2nⁿ⁺¹ = C_2n^n-1. So the total number of valid situation is C_2nⁿ - C_2nⁿ⁺¹, which is catalan number.

Traverse of Binary Tree

//to do