Question

(a) Given a 4×4 grid, how many different paths from (0,0) to (4,4) satisfy the following condition:

• You can only go from (x, y) to either (x+1, y) or (x, y+1)

(b) Given a 4×4 grid, how many different paths from (0,0) to (4,4) satisfy the following condition:

• You can only go from (x, y) to either (x+1, y) or (x, y+1)

• You cannot go to points (x, y) where y > x, in other word, you cannot cross line y = x

(c) How many sequences of 4 pairs of parentheses are mismatched? An example of a matched sequence of paretheses is ()()()(), while a mismatched sequence is )))(((.

Answer 1

(a) To go from (0,0) to (4,4), you will have to take 4 steps right in x axis (say,r), and 4 steps up in y axis (say, u). Thus, we need to find the total number of combinations of 4r and 4u, eg. rrrruuuu. So, for the total 8 places we can select any four place and keep r, while we can keep u in the remaining places. This can be found using the formula for combination: C(n,k)=((k!)/(k! * (n-k)!)). Keeping n=8, k=4, we have C(8,4)=70.

(b) The given question can be understood as: we need to arrange four r and four u in such a way that number of r is always greater than the number of u going from left to right. We can do this using the Catalan number as C(2k,k)/(k+1), ie, C(8,4)/(4+1)=70/5=14.

(c) Number of mismatched paranthesis = Total number of possible combinations of four ( and four ) - Number of matched arrangements. Suppose, we mark the opening parentheses ( as r and the closed parentheses ) as u. Then we can get the total possible combinations using question (a) and number of matched combinations using (b). Thus, number of mismatched paranthesis=70-14=56.