Ballot Problem
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).
SEE ALSO: André's Reflection Method,
Catalan Number,
Staircase
Walk,
TAK Function
REFERENCES:
André, D. "Solution directe du problème résolu par M. Bertrand."
Comptes Rendus Acad. Sci. Paris 105, 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.
Referenced on Wolfram|Alpha:
Ballot Problem
CITE THIS AS:
Weisstein, Eric W. "Ballot Problem." From
MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/BallotProblem.html
Contact the MathWorld Team
aleph0
