Concept

Ballot problem

The question of how likely the eventual winner of a count is to lead at every moment of it. Its answer is the difference of the two vote totals divided by their sum, and the reflection argument that gives it is the same one that counts lattice paths above a diagonal.

Named by 2 essays across 2 fields — each of them below, with the objects they name alongside it.

A path folded about the first time it touches. A walk from 2 to 4 that touches the axis, with the part before its first touch reflected. The reflection is a path from the mirrored start to the same endpoint, and the correspondence is exact.

The path folded at its first touch

Counting the walks that touch a line looks like a question about a walk's whole history. Fold each one where it first touches, and it becomes a question about where walks end up — which is a binomial coefficient, and is already known.

probability · Random walk

A bad path, and the path it reflects to. Two grids, 6 by 5. On the left a monotone path that dips below the diagonal, with its first offending step marked; on the right the same path with everything after that step reflected, which ends one square right and one square below the corner.

Counting the paths that go wrong

The number of good paths across a grid has no obvious formula. The number of bad ones does, because every bad path can be reflected into a path to a different corner, and that reflection is a perfect matching between two sets nobody chose to relate.

discrete · Catalan numbers

Named alongside it

The objects these essays reach for when they reach for this one.

Bijection Binomial coefficient Random walk Reflection principle Catalan numbers Counting-two ways First return Lattice paths Lattice walk

All concepts