Lattice Paths and Ballot Problems

A lattice path is a route on a grid that only moves right or up, one step at a time, from the origin to some target point. The number of distinct paths from $(0,0)$ to $(m,n)$ is simply $\binom{m+n}{m}$, because a path is fully described by choosing which $m$ of the total $m+n$ steps are "rightward" moves (the rest are automatically "upward"). This single formula underlies a large family of classic counting problems in probability and interviews.

The ballot problem is a famous variant: if candidate A receives $a$ votes and candidate B receives $b$ votes in an election with $a > b$, and votes are counted one at a time in random order, what fraction of the possible counting orders have A strictly ahead of B at every single point in the count (not just at the end)? The answer is a clean ratio: $\frac{a-b}{a+b}$. For example, if A wins 3 votes to 1, the probability A is always strictly ahead throughout the count is $\frac{3-1}{3+1} = \frac{1}{2}$.

The connection to lattice paths: represent each A-vote as a right step and each B-vote as an up step, so a vote-counting order is exactly a lattice path, and "A always strictly ahead" means the path never touches the diagonal line except at the very start. Counting such paths is a classic reflection-principle argument, and it's the same machinery that produces the Catalan numbers governing balanced-parentheses and other "never go negative" counting problems.