Catalan number applications - balanced paranthesis, number of binary search trees etc..

An excerpt from wiki (http://en.wikipedia.org/wiki/Catalan_number):

In combinatorial mathematics, the Catalan numbers form a sequence of natural numbers that occur in various counting problems, often involving recursively-defined objects.

The first Catalan numbers for n = 0, 1, 2, 3, … are

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, ...

Some of the applications are:

• C_n is the number of Dyck words of length 2n. A Dyck word is a string consisting of n X's and n Y's such that no initial segment of the string has more Y's than X's (see also Dyck language). For example, the following are the Dyck words of length 6:

         XXXYYY     XYXXYY     XYXYXY     XXYYXY     XXYXYY.

• Re-interpreting the symbol X as an open parenthesis and Y as a close parenthesis, C_n counts the number of expressions containing n pairs of parentheses which are correctly matched:

        ((()))     ()(())     ()()()     (())()     (()())

• C_n is the number of different ways n + 1 factors can be completely parenthesized (or 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))

• Successive applications of a binary operator can be represented in terms of a full binary tree.^[3] (A rooted binary tree is full if every vertex has either two children or no children.) It follows that C_n is the number of full binary trees with n + 1 leaves:

If we want to print all the possible balanced parenthesis - we can solve by below recursive function which prints either "(" or ")" recursively - but while printing make ")" it makes sure that the number of left "(" printed are always >= to number of right parenthesis.

Below is the corresponding code

Code Snippet

128. string[] GetAllPossibleParanthesis_2(int N)
129.         {
130.             var r = this.GetAllPossibleParanthesis_2(N, N, "");
131.             return r;
132.         }
133.         string[] GetAllPossibleParanthesis_2(int left, int right, string s)
134.         {
135.             if((left == 0) && (right==0))
136.             {
137.                 return new string[] { s };
138.             }
139.             Assert.IsTrue(left <= right);
140.             List<string> results = new List<string>();
141.             if (left > 0)
142.             {
143.                 var r = this.GetAllPossibleParanthesis_2(left - 1,
144.                     right, s + "[");
145.                 results.AddRange(r);
146.             }
147.             if(left <= (right-1))
148.             {
149.                 var r = this.GetAllPossibleParanthesis_2(left,
150.                     right-1, s + "]");
151.                 results.AddRange(r);
152.             }
153.             return results.ToArray();
154.         }

Example of how the recursive method generates balanced parenthesized string for 3 pairs

Solving the problem identifying the Catalan recursive relationship

The Catalan numbers satisfy the recurrence relation

for ex, C_n is the number of different ways n + 1 factors can be completely parenthesized
i.e; C0 = 1 (1 factor -> a)
      C1 = 1 (2 factors -> (ab))
      C2 = 2 (3 factors -> (a(bc)), ((ab)c)
Or, C2 = C0*C1 + C1*C0 = { a(bc), (ab)c }
      C3 = 5 (4 factors -> (a(b(cd)), (a((bc)d)), ((ab)(cd)), (((ab)c)d), ((a(bc))d)
Or, C3 = c0*c2 + c1*c1+c2*c0 { a(b(cd)), a((bc)d), (ab)(cd), (a(bc))d, ((ab)c)d

Note: its probably more intuitive from programming perspective if we start the sequence with notation c1 than c0 where c1 represents different ways '1' factor can be completely parenthesized and so on...

Below is the corresponding code where factors are sent as string to the method:

Code Snippet

58. string[] CatalanNumber_GeneratingParanthesizedFactors(string s)
59.         {
60.             s.ThrowIfNullOrWhiteSpace("s");
61.             if(s.Length == 1)
62.             {
63.                 return new string[] {s};
64.             }
65.             var r = this.CatalanNumber_GeneratingParanthesizedFactorsRecursive(
66.                 s);
67.             return r;
68.         }
69.         string[] CatalanNumber_GeneratingParanthesizedFactorsRecursive(string s)
70.         {
71.             if(s.Length == 1)
72.             {
73.                 return new string[] {s};
74.             }
75.             if(s.Length == 2)
76.             {
77.                 string r = "(" + s + ")";
78.                 return new string[] { r };
79.             }
80.             List<string> results = new List<string>();
81.             for (int i = 1; i < s.Length; i++)
82.             {
83.                 var r1 = this.CatalanNumber_GeneratingParanthesizedFactorsRecursive(
84.                     s.Substring(0, i));
85.                 var r2 = this.CatalanNumber_GeneratingParanthesizedFactorsRecursive(
86.                     s.Substring(i));
87.                 foreach(var s1 in r1)
88.                 {
89.                     foreach(var s2 in r2)
90.                     {
91.                         string r = "(" + s1 + s2 + ")";
92.                         results.Add(r);
93.                     }
94.                 }
95.             }
96.             return results.ToArray();
97.         }

 

 All possible balanced parenthesis using Catalan recursive relationship

C_n counts the number of expressions containing n pairs of parentheses which are correctly matched

1, 1, 2, 5, 14, 42, 132, etc...

i.e, c0 = empty (considered one for generalization)

      c1 = []

      c2 = [[]], [][]

      c3 = [[[]]], [[][]], [[]][], [][[]], [][][]

Essentially one need to notice that any correct (balanced) balanced parenthesized strings can be represented with [c']c'' where c' and c'' are valid strings.

i.e, it satisfies Catalan recursive relationship :)

Cn = c0*Cn-1 + C1*Cn-2+....+Cn-2*C1+Cn-1*C0

or in other words,

Cn string = [C0]*Cn-1+[C1]*Cn-2+......+[Cn-2]*C1+[Cn-1]*C0

 

Below is the corresponding code:

 

Code Snippet

98. string[] CatalanNumber_AllPossibleParanthesis(int N)
99.         {
100.             Assert.IsTrue(N >= 0);
101.             if(N==0)
102.             {
103.                 return new string[] {" "};
104.             }
105.             if(N == 1)
106.             {
107.                 return new string[] { "[]" };
108.             }
109.             
110.             List<string> results = new List<string>();
111.             for (int i = 0; i <= (N - 1); i++)
112.             {
113.                 var r1 = this.CatalanNumber_AllPossibleParanthesis(i);
114.                 var r2 = this.CatalanNumber_AllPossibleParanthesis(N - 1 - i);
115.                 
116.                 foreach (var s1 in r1)
117.                 {
118.                     foreach (var s2 in r2)
119.                     {
120.                         //[c']c" - will be of the form
121.                         string r = "[" + s1.Trim() + "]" + s2.Trim();
122.                         results.Add(r);
123.                     }
124.                 }
125.             }
126.             return results.ToArray();
127.         }

Number of full binary trees, binary search trees, binary trees etc.

C_n is the number of full binary trees with n + 1 leaves:

Note: basically only the structure is taken into account, not the data.

Then, one can say C0 = 1 (number of binary trees with '1' leaf)
                              C1 = 1 (number of binary trees with '2' leaves)
                              C3 = C0*C1 (number of binary trees on left with '1' leaf and on right with '2' leaves) + C1*C0 (vice versa)
So, one can define Cn = C0*Cn-1 ('1' leaf on left and 'n' leaves on right) + c1*Cn-2+....+Cn-2*C1 (n-1 leaves on left and 2 on right)+Cn-1*C0 (n leaves on left and 1 leaf on right)

Cn is the total number of binary search trees that can be constructed from given 'N' distinct elements

i.e, C0 = 1 (empty tree)
      C1 = 1 (with one element)
      C2 = 2 (with two elements)
      C3 = C0*C2 (none on left and 2 on right) + C1*C1 (using one element on both sides)+C2*C0

i.e, it satisfies Catalan recursive function, and Cn is nothing but Catalan number.

No. of structurally equivalent binary trees with given 'N' nodes is Cn as well. And by taking the data into consideration, then total number of binary trees are N!*nthCatalanNumber.

Below is the code to generate total number of binary search trees (Catalan Number):
 

Code Snippet

13. public int DP_Catalan_TotalBinarySearchTrees(int N)
14.         {
15.             if (N == 0)
16.             {
17.                 return 1;
18.             }
19.             if (N == 1)
20.             {
21.                 return 1;
22.             }
23.             int[] DP_Catalan_Cache = new int[N + 1];
24.             DP_Catalan_Cache[0] = 1;
25.             DP_Catalan_Cache[1] = 1;
26.             for(int i = 2;i<=N; i++)
27.             {
28.                 int sum = 0;
29.                 for(int j=0;j<i;j++)
30.                 {
31.                     sum += (DP_Catalan_Cache[j]*DP_Catalan_Cache[i-1-j]);
32.                 }
33.                 DP_Catalan_Cache[i] = sum;
34.             }
35.             return DP_Catalan_Cache[N];
36.         }
37.         public int GetCatalan_TotalBinarySearchTrees(int N)
38.         {
39.             if(N==0)
40.             {
41.                 return 1;
42.             }
43.             if(N==1)
44.             {
45.                 return 1;
46.             }
47.             int sum = 0;
48.             for(int i = 1;i<=N;i++)
49.             {
50.                 int totalLeftTrees = this.GetCatalan_TotalBinarySearchTrees(i - 1);
51.                 int totalRightTrees = this.GetCatalan_TotalBinarySearchTrees(N - i);
52.                 sum += (totalLeftTrees * totalRightTrees);
53.             }
54.             return sum;
55.         }

Below are the corresponding Unit Tests

 

Code Snippet

155. [TestCategory(Constants.Recursion)]
156.         [TestMethod]
157.         public void AllPossibleParanthesisTests()
158.         {
159.             int[] CatalanNumbers = new int[] { 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796 };
160.             for(int i=1;i<=10;i++)
161.             {
162.                 var results2 = this.GetAllPossibleParanthesis_2(i);
163.                 Assert.AreEqual(results2.Length, CatalanNumbers[i - 1]);
164.                 var results = this.CatalanNumber_AllPossibleParanthesis(i);
165.                 Assert.AreEqual(results.Length, CatalanNumbers[i - 1]);
166.                 Debug.WriteLine("-----------------------------------------------");
167.                 foreach (string s in results2)
168.                 {
169.                     Assert.IsTrue(results.Any(rs => rs.Equals(s)));
170.                 }
171.             }
172.         }

Code Snippet

16. [TestMethod]
17.         public void CatalanNumber_GeneratingParanthesizedFactorsTests()
18.         {
19.             var CatalanNumbers = new int[] { 1, 1, 2, 5, 14, 42, 132, 429,
20.                 1430, 4862, 16796 };
21.             string input = "";
22.             for (int i = 1; i <= 10; i++)
23.             {
24.                 input += i;
25.                 var results2 = this.CatalanNumber_GeneratingParanthesizedFactors(input);
26.                 Assert.AreEqual(results2.Length, CatalanNumbers[input.Length-1]);
27.                 Debug.WriteLine("-----------------------------------------------");
28.                 foreach (string ss in results2)
29.                 {
30.                     Debug.WriteLine(ss);
31.                 }
32.             }
33.             string s = "a";
34.             var r = this.CatalanNumber_GeneratingParanthesizedFactors(s);
35.             Assert.AreEqual(r.Length, 1);
36.             Assert.AreEqual(s, r[0]);
37.             s = "ab";
38.             r = this.CatalanNumber_GeneratingParanthesizedFactors(s);
39.             Assert.AreEqual("(ab)", r[0]);
40.             s = "abc";
41.             r = this.CatalanNumber_GeneratingParanthesizedFactors(s);
42.             string[] output = new string[] { "(a(bc))", "((ab)c)" };
43.             Assert.AreEqual(2, r.Length);
44.             foreach(var o in output)
45.             {
46.                 Assert.AreEqual(1, r.Where(rs => (rs == o)).Count());
47.             }
48.             s = "abcd";
49.             r = this.CatalanNumber_GeneratingParanthesizedFactors(s);
50.             
51.             output = new string[] { "(a(b(cd)))", "(a((bc)d))", "((ab)(cd))", "(((ab)c)d)", "((a(bc))d)"};
52.             Assert.AreEqual(5, r.Length);
53.             foreach (var o in output)
54.             {
55.                 Assert.AreEqual(1, r.Where(rs => (rs == o)).Count());
56.             }
57.         }

Code Snippet

57. [TestMethod]
58.         public void Catalan_TotalBinarySearchTreesTests()
59.         {
60.             var CatalanNumbers = new int[] { 1, 1, 2, 5, 14, 42, 132, 429,
61.                 1430, 4862, 16796 };
62.             for(int i =0;i<CatalanNumbers.Length;i++)
63.             {
64.                 int n = this.GetCatalan_TotalBinarySearchTrees(i);
65.                 Assert.AreEqual(CatalanNumbers[i], n);
66.                 int n1 = this.DP_Catalan_TotalBinarySearchTrees(i);
67.                 Assert.AreEqual(n, n1);
68.             }
69.         }