A Game of Cat and Mouse

This will be the final post in the series on counting principles. Here, I wish to deal with a strange idea of balancing parentheses. If that seems like a strange term itself, let me explain. An arrangement of n left parentheses ‘(‘ and n right parentheses ‘)’ is said to be balanced if, for every right parenthesis, there exists a corresponding left parenthesis before it. Examples of balanced arrangements are

where corresponding colors indicate the parentheses that pair up. Examples of unbalanced arrangements are

where the black colored right parenthesis indicate the first unbalance parenthesis for which there is no left parenthesis before it. All the parentheses after that are colored dark brown because, after the unbalanced parenthesis, there is no point trying to pair up the parentheses.

The problem we are faced with it this: Given n pairs of left and right parentheses, how many unbalanced arrangements are there?

Consider an unbalanced arrangement. We proceed from left to right until we encounter the first unbalanced right parenthesis. This must necessarily be in an odd position, since for the right parenthesis to be unbalanced, there must be totally one more right parentheses than left parentheses.

Suppose the position of the unbalanced parenthesis is 2k + 1. Hence there are k balanced pairs to the left of the unbalanced parenthesis. And there are 2n – 2k – 1 parentheses to the right of it. Of these there is one extra left parenthesis than right parenthesis. So there are n – k left parentheses and n – k – 1 right parentheses to the right of the unbalanced parenthesis.

Let us reverse all of these 2n – 2k – 1 parentheses, making the left parentheses into right ones and vice versa. Now there will be n – k – 1 left parentheses and n – k right parentheses to the right of the unbalanced parenthesis.

So now there will be k + n – k – 1 = n – 1 left parentheses and k + n – k + 1 = n + 1 right parentheses. Note that this holds true regardless of where we located the first unbalanced parenthesis! Hence, the problem has boiled down to placing n – 1 left parentheses in 2n positions. This can obviously be done in ²ⁿC_{n – 1} ways.

Let us consider some examples to ensure we have done this correctly. Suppose n = 5 and k = 2. Then the unbalanced bracket is in the 5^th position. So we have

or some such arrangement, where we have k = 2 pairs of balanced pairs (in green) to the left of the unbalanced right parenthesis (in red). To the right of this unbalanced parenthesis we have 2n – 2k – 1 = 5 parentheses, n – k = 3 of them being left parentheses (in purple) and n – k – 1 = 2 right parentheses (in orange). After reversing the parentheses to the right of the unbalanced parenthesis we will have the arrangement

where there are n – k – 1 = 2 left parentheses (in orange) and n – k = 3 right parentheses (in purple) to the right of the original unbalanced parenthesis (in red). So now there are totally n – 1 = 4 left parentheses (occupying positions 1, 3, 9 and 10) and n + 1 = 6 right parentheses (occupying positions 2, 4, 5, 6, 7 and 8).
Suppose, instead that n = 5 and k = 3. Then we have

or some such arrangement, where we have k = 3 pairs of balanced pairs (in green) to the left of the unbalanced right parenthesis (in red). To the right of this unbalanced parenthesis we have 2n – 2k – 1 = 3 parentheses, n – k = 2 of them being left parentheses (in purple) and n – k – 1 = 1 right parentheses (in orange). After reversing the parentheses to the right of the unbalanced parenthesis we will have the arrangement

where there are n – k – 1 = 1 left parentheses (in orange) and n – k = 2 right parentheses (in purple) to the right of the original unbalanced parenthesis (in red). So now there are totally n – 1 = 4 left parentheses (occupying positions 1, 3, 5 and 10) and n + 1 = 6 right parentheses (occupying positions 2, 4, 6, 7, 8 and 9).

Comparing the cases for k = 2 and k = 3 we can see that the number of left and right parentheses after reversing remains the same. The only thing that changed is the positions of the left and right parentheses. So it is simply an issue of choosing n – 1 positions for the left parentheses out of the existing 2n positions. The number of ways in which this can be done is

Let us consider a question. A class has 51 students. In an election for class representative, 3 candidates A,B, and C contest the elections. When the votes are counted it is found that A secured 26 votes, B 20 votes, and C 5 votes. If the counting of ballots was done in a random order, in how many ways could the votes have been counted so that at every stage A had more votes than both B and C?

Here the votes for B and C do not actually differ. We can consider them together. Hence, A received 26 votes and the opponents received 25 votes. In order for A to be ahead of both B and C, A should have received the first vote. Now, we can view votes for A as left parentheses and votes for thee opponents as right parentheses. For A to be ahead after the first vote, the votes should be ‘balanced’. The total number of arrangements of the 25 remaining votes for A out of the remaining 50 votes is ⁵⁰C₂₅. However, the number of unbalanced arrangements of votes is ⁵⁰C₂₄. Hence, the number of ways in which A would have always been ahead of the opponents is ⁵⁰C₂₅ – ⁵⁰C₂₄ = 126,410,606,437,752 – 121,548,660,036,300 = 4,861,946,401,452.

So, allow me to leave you with a question. Tom the cat and Jerry the mouse are playing a game on the computer. Tom launches applications while Jerry hits ALT-F4 to terminate the applications. If Jerry hits ALT-F4 when no application is running, the computer will shut down. If both of them work randomly, what is the probability that Jerry manages to shut down the computer before Tom launches 5 applications? You can find the solution here.

With that we conclude the series on counting principles. I will move to solving some problems that intrigue me from the next post onward for a few weeks before I start another series.