Counting votes, as long as one has more votes all the way through.

Question

1. Two competitors won $n$ votes each. How many ways are there to count the $2n$ votes, in a way that one competitor is always ahead of the other?

2. One competitor won $a$ votes, and the other won $b$ votes. $a>b$. How many ways are there to count the votes, in a way that the first competitor is always ahead of the other? (They can have the same amount of votes along the way)

I know that the first question is the same as the number of different legal strings built of brackets, which is equal to the Catalan number; $\frac{1}{n+1}{2n\choose n}$, by the proof with the grid.

I am unsure about how to go about solving the second problem.

Answer 1

We can use a similar idea to the solution to #1:

The total number of ways the votes can be counted is $a+b \choose a$, so we have to subtract the number of ways competitor B can get ahead of competitor A:

In any count where B gets ahead of A, change all the votes up to and including the first vote where B takes the lead; this will give a count where A gets $a+1$ votes and B gets $b-1$ votes.

Conversely, in any count where A gets $a+1$ votes and B gets $b-1$ votes, changing all the votes up to and including the first vote where A gets the lead gives a vote sequence of the first type.

Thus the answer is $\binom{a+b}{a}-\binom{a+b}{a+1}$.

After referring to the link provided by Brian Scott, I realized that I am answering a slightly different question, which is the number of ways the votes can be counted so that A never gets behind B in the count, not the number of ways that A always remains ahead of B. (In #1, the answer is $C_n$ to this question, not to the question in which A always remains ahead of B.)

For the version of the problem as stated, use the fact that A must get the first vote and then apply the same argument to the remaining $a+b-1$ votes.

Answer 2

This is Bertrand’s ballot problem; Bertrand’s ballot theorem gives the probability that a randomly chosen counting order has the desired property. André’s proof of Bertrand’s ballot theorem proceeds by counting the desired sequences, using a technique similar to that usually used to solve the first problem; since you’ve already seen that argument, you can probably fill in the details in André’s argument as sketched in the linked article.