The Ballot Problem

Marc Renault

This web page is designed to accompany the article Lost (and Found) in Translation: André’s Actual Method and its Application to the Generalized Ballot Problem. This article appeared in the American Mathematical Monthly, April 2008.

I gave a 15-minute talk on this at MathFest in August 2007. Here are the slides.

I have also written the article Four Proofs of the Ballot Theorem, which appeared in Mathematics Magazine, December 2007.

The Ballot Problem

Suppose that candidates A and B are in an election. A receives a votes and B receives b votes, with a > b.

The Ballot Problem: How many ways can the a + b votes be arranged so that A maintains a lead throughout the counting of the ballots?

Answer: .

The Generalized Ballot Problem: Suppose a > kb for some positive integer k. How many ways can the a + b votes be arranged so that A always has more than k times as many votes as B throughout the counting of the ballots?

Answer: .

(Some authors refer to both of the above as the ballot problem, and use “generalized ballot problem” for something even more general.)

Web Resources

MathWorld

Biography of J. Bertrand

Articles

The following articles were cited in Lost (and Found) in Translation…

The three article from 1887 were found at http://math-doc.ujf-grenoble.fr/RBSM/.

The two articles from 1923 were found at http://retro.seals.ch/digbib/home.

1887 J. Bertrand, Solution d’un problème, Comptes Rendus de l’Académie des Sciences, Paris 105 (1887) p. 369.
Original Translation

1887 É. Barbier, Généralisation du problème résolu par M. Bertrand, Comptes Rendus de l’Académie des Sciences, Paris 105 (1887) p. 407.
Original Translation

1887 D. André, Solution directed du problème résolu par M. Bertrand, Comptes Rendus de l’Académie des Sciences, Paris 105 (1887) 436–437.
Original Translation

1923 J. Aebly, Démonstration du problème du scrutin par des considérations géométriques, L’enseignement mathématique 23 (1923) 185–186
Original Translation

1923 D. Mirimanoff, A propos de l’interprétation géométrique du problème du scrutin, L’enseignement mathématique 23 (1923), 187–189.
Original Translation

1947 A. Dvoretzky and Th. Motzkin, A problem of arrangements, Duke Math. J. 14 (1947) 305–313.

1991 P. Hilton and J. Pedersen, Catalan numbers, their generalizations, and their uses, Math. Intell. 13 (1991) 64–75.

2003 I.P. Goulden and Luis G. Serrano, Maintaining the Spirit of the Reflection Principle when the Boundary has Arbitrary Integer Slope, J. Combinatorial Theory (A) 104 (2003) 317-326.
Article is available from Goulden’s web site.

Some Sources Citing the Reflection Method and André

Please note: Many excellent articles and reputable sources claim (incorrectly) that André used the reflection method. I have created this list not to question the quality of the sources, but only to show the prevalence of the misattribution. Sources are listed starting with the most recent.

• MathWorld - Claims André used the reflection method.
  
  
• I.P. Goulden and Luis G. Serrano, Maintaining the Spirit of the Reflection Principle when the Boundary has Arbitrary Integer Slope, J. Combinatorial Theory (A) 104 (2003) 317-326.
  p. 2: “André gave a direct geometric bijection between the subset of bad paths and the set A of all paths from (1, -1) to (m, n), and the result then follows immediately, since |A| = C(m + n, m – 1). In the bijection, the initial portion of the path up to the first point that lies on the line y = x – 1 is reflected about the line y = x – 1, and so André’s beautiful method of proof is called the reflection principle.”
  
  
• J.H. Van Lint and R.M. Wilson, A Course in Combinatorics, Cambridge University Press, 2001.
  p. 151: “The reflection principle of Fig. 14.2 was used by the French combinatorialist D. André (1840-1917) in his solution of Bertrand’s famous ballot problem…”
  
  
• I. Karatzas and S.E. Shreve, Brownian Motion and Stochastic Calculus, Springer, 1998.
  When introducing the reflection principle, they cite P. Lévy 1948 p. 293 (see below). Then they write “Here is the argument of Désiré André…” and proceed with the reflection method.
  
  
• H. Bauer, Probability Theory, Walter de Gruyter, Berlin, New York, 1996.
  p. 231: “In the literature, this reflection principle is usually attributed to D. André (1840-1918). It occurs in the form of such a geometric argument in André [1887].”
  
  
• P. Hilton and J. Pedersen, Catalan numbers, their generalizations, and their uses, Math. Intell. 13 (1991) 64–75.
  Claims André used the reflection method.
  
  
• D. Stanton and D. White, Constructive Combinatorics, Springer-Verlag, New York, 1986.
  Attributes the reflection method to André.
  
  
• D. Zeilberger, André’s reflection proof generalized to the many-candidate ballot problem, Discrete Mathematics 44 (1983) 325-326.
  Remarks that André used the reflection method.
  
  
• L. Comtet, Advanced Combinatorics, the Art of Finite and Infinite Expressions, D. Reidel, Dordrecht-Holland, 1974.
  
  I don’t believe Comtet actually means to attribute the reflection method to André, though he may be unclear on this matter. After posing the ballot problem he writes, “This is the famous ballot problem formulated by [Bertrand, 1887]; we give the elegant solution of [André, 1887].” He then goes on to write “We first formulate the principle of reflection, which essentially is due to André.” Comtet includes references to many of André’s works. His use of the word “essentially” seems to indicate that he recognizes a subtle distinction.
  
  
• A. Papoulis, Probability, Random Variables, and Stochastic Processes, McGraw-Hill, New York 1965.
  
  On page 505 Papoulis writes “The reflection principle† (of Désiré André), loosely phrased, says that the functions of a Wiener-Lévy process that cross a line w = d (this line will be denoted by L_d) continue on symmetrical paths.” At the dagger, Papoulis includes a footnote citing J.L. Doob, Stochastic Processes (see below).
  
  
• W. Feller, An Introduction to Probability Theory and Its Applications, Second Edition, John Wiley & Sons, Inc., New York 1957.
  
  p. 66. Feller introduces the ballot problem then writes in the footnote: “For the history and literature see A. Dvoretzky and T. Motzkin, A problem of arrangements, Duke Mathematical Journal, vol. 14 (1947), pp. 305-313. As these authors point out, most of the formally different proofs in reality use the reflection principle (lemma 1 of section 2), but without the geometric interpretation this principle loses its simplicity and appears as a curious trick.”
  
  p. 70. Upon considering the reflection method, Feller writes in the footnote “The probability literature attributes this method to D. André (1887). The text reduces it to a lemma on random walks. The classical difference equations of random walks (chapter XIV) closely resemble differential equations, and the reflection principle (even a stronger form of it) is familiar in that theory under the name of Lord Kelvin’s method of images.”
  
  In the first edition of this book (1950) no mention is made of André or the reflection principle.
  
  
• J.L. Doob, Stochastic Processes, John Wiley & Sons, Inc., New York 1953.
  
  On page 393, in a section on Brownian movement process, Doob writes “The exact evaluation (2.3) and similar exact evaluations are easily made, once sample function continuity has been proved, using what is known as the reflection principle of Désiré André.”
  
  In the preface, Doob thanks Feller for reading and commenting on earlier versions of the manuscript. Perhaps this is why Feller includes the reflection principle in the second edition of his book, but not the first?
  
  
• P. Lévy, Processus Stochastiques et Mouvement Brownien Gauthier-Villars, Paris, 1948. (?)
  
  In the book Brownian Motion and Stochastic Calculus by Shreve and Karatzas (Springer 1998), page 293 of this Lévy source is cited. However, I’ve been unable to find any reference to André or the reflection principle in Lévy.
  
  
• Are there any references to André and the reflection principle prior to 1953?