Catalan Number

[ythy]

O(2^N)

function catalan(n:number):number{
  if(n == 0 || n == 1 )
    return 1;
  let result = 0;
  for(let i = 0; i < n; i++){
    result += catalan( i ) * catalan( n - 1 - i );
  }
  return result;
}

O(N²)

function catalanDynamic(n: number): number {
  let dp:number[] = [ 1, 1 ];
  for (let i = 2; i <= n; i++) {
    dp[i] = 0;
    for (let j = 0; j < i; j++) {
      dp[i] += dp[j] * dp[ i - 1 - j];
    }
  }
  return dp[n];
}

[ythy]

Basic Description

The nth Catalan number is defined as

The binomial coefficientpronounced as n choose r, represents the number of possible combinations of r objects from a collection of n objects:

Therefore,

Example:

Catalan numbers could be described in various but equivalent ways. If you transform the first formula just a little bit, you will get another useful formula of Catalan numbers.

[ythy]

Balanced Parentheses

In the application Balanced Parenthese, it is already known that for each open parenthesis, there is a close parenthesis. Now, let's try to find a pattern in these paired parentheses with example n = 3:

( (( )) ) - ( ( )( ) ) - (( )) ( ) - ( ) (( )) - ( )( )( )

it is certain that there is at least a pair of parentheses, and we will fix it in collection A. Thus, the simplest form where n = 1 is:

For values of n that are greater than 1, we simply add more pairs of parentheses inside the fixed black parenthese to collection A, and place the rest in collection B. In this way, both collection A and B are able to contain up to n - 1 pairs of parentheses (the black parentheses in the base form does not count as one of them). If collection A contains k pairs, then it is not hard to find that there are n - ( k + 1) pairs in collection B.

What is the purpose of separating the parentheses into two collections? Well, we want to two collections A and B for the purpose of counting the combinations of parentheses systematically, that is, if A has 0 pairs, B has n - 1 pairs; A 1 pair, and B n - 2 pairs; A 2 pairs, and B n - 3 pairs,

表格

Number of Pairs Contained in A	Number of Pairs Contained in B	Illustration	Number of Solutions
0	n - 1
1	n - 2
n - 1	0

Add up all of the situations, and we get the total number:

[ythy]

Grouping with Parenthesis

P1

P1 = 1

P2

P2 = 1 as there is only one way to do the grouping:

(ab)

P3

P3 = 2 as there are two groupings:

a(bc):   (ab)c;    

it will also be

(P1)(P2);  (P2)(P1);

P4

P4 = 5 as there are 5 groupings:

a(b(cd));  a((bc)d);  (ab)(cd);  (a(bc))d;  ((ab)c)d:

it will also be

(P1)(P3);  (P2)(P2); (P3)(P1)

conclusion

which can be used to compute Pn once we have computed P1; P2; : : : ; Pn-1. The rst several are

n	2	3	4	5	6	7	8
Pn	1	2	5	14	42	132	429

However this is not a trivial proof.