**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**

**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*) continue on symmetrical paths.” At the dagger, Papoulis includes a footnote citing J.L. Doob,_{d}*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?