[COMP2121] Bertrand's Ballot Problem

Description

Suppose there are $x$ votes for $A$ and $y$ notes for $B$, and $x>y$. How many sequences are there of revealing the votes such that the number votes for $A$ is always strictly bigger than that for $B$?

Solution (by reflection)

First, we draw the process of revealing the votes using line charts (the horizontal axis represents the number of votes revealed, the vertical axis represents $x_cur-y_cur$):

Define the grand set $\Omega$ to be the set of sequences that starts from $0$ and ends at $x-y$. A valid sequence drawn in such a way should never touch the horizontal axis. 

Note that the first vote must be a "+1". Let $A$ denote the set of sequences whose first element is "+1" and $B$ denote the set of sequences whose first element is "+1" but not valid (touches 0 at some point). Then the answer would be

$$|A| - |B|$$

It is easy to see that

$$|A| = \frac{(x+y-1)!}{(x-1)!y!}$$

Now use the technique of bijection to compute $|B|$, i.e. find an easily-computable set $C$ such that sequences in $B$ and $C$ has an one-to-one relation.

We attempt to find $C$ in such a way: for every sequence in $B$, reflect the prefix before the line first touches 0 with respect to the horizontal axis to get a sequence in $C$:

By observing, we try to define $C$ to be the set of sequences whose first element is "-1" (and ends at $x-y$). Then, according to the mapping, different sequences in $B$ will result in different sequences in $C$, so the mapping is injective. Also, for every sequence in $C$, there exists a sequence in $B$ which is obtained by reflecting $C$'s prefix before first touching 0 (such prefix always exists because it goes from $-1$ to $x-y$), so the mapping is bijective. Therefore, we successfully find the $C$ we want.

Now compute $|C|$. Suppose in the next $x+y-1$ steps, there are $a$ "+1"s and $b$ "-1"s, then:

$$\left\{\begin{matrix}a+b=x+y-1 \\-1+a-b=x-y\end{matrix}\right. \Rightarrow \left\{\begin{matrix}a=x \\b=y-1\end{matrix}\right.$$

Thus,

$$|C|=\frac{(x+y-1)!}{x!(y-1)!}$$

Alternatively, $C$ is the complement of $A$:

$$|C|=|\Omega|-|A|=\frac{(x+y)!}{x!y!}-\frac{(x+y-1)!}{(x-1)!y!}=\frac{(x+y-1)!}{x!(y-1)!}$$

Finally, we can compute the answer:

$$|A|-|B|=|A|-|C|=\frac{(x-y)(x+y-1)!}{x!y!}$$