Ballot Problem

Suppose and are candidates for office and there are voters, voting for and for . In howmany ways can the ballots be counted so that is always ahead of or tied with ? The solution is a CatalanNumber .

A related problem also called ``the'' ballot problem is to let receive votes and votes with . Thisversion of the ballot problem then asks for the probability that stays ahead of as the votes are counted (Vardi1991). The solution is , as first shown by M. Bertrand (Hilton and Pedersen 1991). Another elegant solutionwas 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 withthe ballot problem (Vardi 1991).

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. 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 Archief voor Wiskunde 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.

• Abelian Function
• Abelian Group
• Abelian Integral
• Abelian Variety
• Abel's Curve Theorem
• Abel's Functional Equation
• Abel's Identity
• Abel's Impossibility Theorem
• Abel's Inequality
• Abel's Irreducibility Theorem
• Abel's Lemma
• Abel's Test
• Abel's Theorem
• Abel's Uniform Convergence Test
• Abel Transform
• Abhyankar's Conjecture
• Ablowitz-Ramani-Segur Conjecture
• Abscissa
• Absolute Convergence
• Absolute Deviation
• Absolute Error
• Absolute Geometry
• Absolutely Continuous
• Absolute Pseudoprime
• Absolute Square