Counting Ballots That Never Fall Behind
The problem
In an election, candidate A receives exactly votes and candidate B receives exactly . Votes are counted one at a time in a random order. How many of the possible orders are such that A is never behind B at any point during the count?
- 'Never behind' means that after every single vote counted, the number of A votes is at least the number of B votes.
- Orders are distinguished by the sequence of A and B labels, not by which individual voter cast which vote.
Take a minute
Reveal hint 1
Encode each order as a path of steps that move right for an A vote and up for a B vote, and look for the paths that never go above the diagonal.
Reveal hint 2
Count the paths that do cross the diagonal by reflecting the part before the first crossing.
Solution
Answer orders, which is the Catalan number .
Derivation
-
Encode the count as a lattice path.
-
Translate the condition.
-
Count the failing paths by reflection.
-
Count the reflected paths.
-
Subtract.
-
Recognise the Catalan number.