5. (a) Let Cn denote the number of ways of writing a valid list of open and clos

Question

5. (a) Let Cn denote the number of ways of writing a valid list of open and closed parentheses of length 2n (valid means that at any point along the list, the number of open parentheses must be greater than or equal the number of closed parentheses In the case of n 3, there are 5 valid configurations: (0), (0) 0,000, (00), 0(0) With C 1, provide a combinatorial proof that Cr, C (b) Show that On also determines the number of paths in the plane from (0,0) to (n,n) e N x N, that don't cross the main diagonal (y T) if each step in the path is of the form (1,0), or (0, 1) (i.e unit distance due east or due north)

Explanation / Answer

a.)

Ck = No. of ways of arranging the valid string of open and closed paranthesis of length 2k

Cn-k = No. of ways of arranging the valid string of open and closed paranthesis of length 2(n-k)

By multiplication rule -

No. of ways of concatenation of these two strings formed S = CkCn-k which has length 2(k+n-k) = 2n

Consider string of length 2n+2

All the string will only form the following two types of string -

1. Either we enclose the string S in paranthesis . i.e. (S)    OR   

2. We put two valid paranthesis after S i.e. S() ; where String S is as defined above

Hence total number of ways of forming a valid string of length

= 2C0Cn + 2C1Cn-1+ 2C2Cn-1 .... + 2Cn/2 -1Cn/2+1

= C0Cn + C1Cn-1+ ..... CkCn-k .... + CnC0

b.)

To reach from (0,0) to (n,n) the no. of paths of the form (1,0) (Unit distance due east) should be same as the no. of paths of the form (0,1) (Unit distance due east)

Also we need to avoid the cases of diaognal crossing

Hence, we get two cases -

1. If we start from (1,0) initially then the number of east steps should always be >= number of north steps

Lets map

one east step = (

and one north step = )

If we start from first east step and reach a total of n steps then it is equivalnet of saying the valid paranthesis of length n

Hence total number of ways of this case = Cn/2

2. Similarly,

If we start from (0,1) initially then the number of north steps should always be >= number of east steps

In this case we do just the opposite . Lets map

one east step = )

and one north step = (

If we start from first north step and reach a total of n steps then it is equivalnet of saying the valid paranthesis of length n

Hence total number of ways of this case = Cn/2

Total number of ways = Cn/2 + Cn/2 = 2Cn/2 = Cn

Related Questions

Navigate

• Browse (All)
• Browse 5
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.