Ballot Problem

Suppose A and B are candidates for office and there are 2n voters, n voting for A and n for B. In how many ways can the ballots be counted so that B is never ahead of A? The solution is a Catalan number C_n.

A related problem also called "the" ballot problem is to let A receive a votes and B b votes with a>=b. This version of the ballot problem then asks for the probability that A stays ahead of B as the votes are counted (Vardi 1991). The solution is (a-b+1)/(a+1), 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

Explore with Wolfram|Alpha


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.

Subject classifications