Suppose
and
are candidates for office and there are voters, voting for and for . In how many ways can the ballots be counted so that is never ahead of ? The solution is a Catalan number.
A related problem also called "the" ballot problem is to let receive votes and
votes with .
This version of the ballot problem then asks for the probability that stays ahead of as the votes are counted (Vardi 1991). The solution is , as first shown by M. Bertrand
(Hilton and Pedersen 1991). Another elegant solution was provided by André
(1887) using the so-called André's
reflection method.
The problem can also be generalized (Hilton and Pedersen 1991). Furthermore, the TAK function is connected with the ballot problem
(Vardi 1991).
André, D. "Solution directe du problème résolu par M. Bertrand." Comptes Rendus Acad. Sci. Paris105,
436-437, 1887.Ball, W. W. R. and Coxeter, H. S. M.
Mathematical
Recreations and Essays, 13th ed. New York: Dover, p. 49, 1987.Carlitz,
L. "Solution of Certain Recurrences." SIAM J. Appl. Math.17,
251-259, 1969.Comtet, L. Advanced
Combinatorics: The Art of Finite and Infinite Expansions, rev. enl. ed. Dordrecht,
Netherlands: Reidel, p. 22, 1974.Feller, W. An
Introduction to Probability Theory and Its Applications, Vol. 1, 3rd ed.
New York: Wiley, pp. 67-97, 1968.Hilton, P. and Pedersen, J. "The
Ballot Problem and Catalan Numbers." Nieuw Arch. Wisk.8, 209-216,
1990.Hilton, P. and Pedersen, J. "Catalan Numbers, Their Generalization,
and Their Uses." Math. Intel.13, 64-75, 1991.Kraitchik,
M. "The Ballot-Box Problem." §6.13 in Mathematical
Recreations. New York: W. W. Norton, p. 132, 1942.Motzkin,
T. "Relations Between Hypersurface Cross Ratios, and a Combinatorial Formula
for Partitions of a Polygon, for Permanent Preponderance, and for Non-Associative
Products." Bull. Amer. Math. Soc.54, 352-360, 1948.Vardi,
I. Computational
Recreations in Mathematica. Redwood City, CA: Addison-Wesley, pp. 185-187,
1991.
and 
are candidates for office and there are 
voters, 
voting for 
and 
for 
. In how many ways can the ballots be counted so that 
is never ahead of 
? The solution is a Catalan number 
.
receive 
votes and 
votes with 
.
This version of the ballot problem then asks for the probability that 
stays ahead of 
as the votes are counted (Vardi 1991). The solution is 
, as first shown by M. Bertrand
(Hilton and Pedersen 1991). Another elegant solution was provided by André
(1887) using the so-called André's
reflection method.
