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).
See also André's Reflection Method, Catalan Number, 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. 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.
- Fence
- Fence Poset
- Ferguson-Forcade Algorithm
- Fermat 4n+1 Theorem
- Fermat Compositeness Test
- Fermat Conic
- Fermat Difference Equation
- Fermat Diophantine Equation
- Fermat Equation
- Fermat-Euler Theorem
- Fermatian
- Fermat-Lucas Number
- Fermat Number
- Fermat Number (Lucas)
- Fermat Point
- Fermat Polynomial
- Fermat Prime
- Fermat Pseudoprime
- Fermat Quotient
- Fermat's Algorithm
- Fermat's Congruence
- Fermat's Conjecture
- Fermat's Factorization Method
- Fermat's Last Theorem
- Fermat's Lesser Theorem