In the last post I showed how to count the number of valid vote sequences given that candidate ends up with only one extra vote over candidate . In general, candidate may end up with votes. How do the counts change?

In terms of balanced parantheses this means we have extra open parantheses to make use of. Let’s say and then

1. There are ways to arrange votes for each candidate

2. For each of the valid ways we can insert an extra open paranthesis in possible places. After this, we can insert the next extra open paranthesis in possible places. So, we now have arrangements.

3. The last extra parantheses we know we have to place it at the beginning. But there are choices for the first paranthesis. So now have possible arrangements.

4. Finally, since the extra parantheses are also indistinguishable we have to divide by .

Thus the number of ways to arrange votes for candidate and votes for candidate where candidate always has the higher number of votes is

The probability that candidate always has the higher number of votes than candidate and ends up with and votes respectively is

We have in fact arrived at the solution without the use of martingales. Next time, let’s see why this example is used in the chapter on martingales.