Mohanty: Lattice Path Counting and Applications (1979)

This book contains quite a lot of interesting material on the combinatorics of paths through two-dimensional grids.

Unfortunately, it's also quite stingy with the explanations, and way too many important things are just brushed off as simple, trivial, obvious, and easy. This makes it quite difficult to use if you're not already familiar with the subject.

The Ballot Problem and Path Counting

One of the central problems that have kicked off the field around the turn of the last century was the ballot problem. In one version, this can be formulated as follows:

If candidate A and B have received n and m votes in an election, respectively, what is then the probability that the losing candidate will lead at some point during the ballot counting process?

To answer this question, we have to come up with a way to count all the possible ways in which the ballots can be sorted, and then count the subset in which the losing candidate leads the count at some point.

Both of these tasks are solved more easily when we think of the counting as a unit-step path through a rectangle of dimensions n x m, beginning at (0, 0) and ending at (n, m). Such a path will consist of n + m steps, corresponding to the fact that every ballot has to be counted exactly once.

Putting the ballots in some order thus corresponds to deciding when you want to walk upwards rather than to the right. Since there are n ballots supporting candidate A and a grand total of n + m, the number of choices is thus the binomial coefficient C(n + m, n) = C(n + m, m). This correspondence is also explained in detail in the first chapter of Victor Bryant's textbook.

Conjugation and Misleading Counts

The other figure we need is more difficult to count, but the lattice path representation helps a lot. Assuming that n > m, we are looking for the number of paths which at some point touches the line x = y – 1, i.e., y = x + 1. These paths corresponds to ballots counts in which the losing candidate leads by at least one vote at least once.

The crucial trick to finding the number of such paths is to define the notion of the conjugate path of a path touching the line. You obtain the conjugate of a path that touches the line y = x + 1 at a point p by replacing the section preceding p by its mirror image around y = x + 1.

This operation always transforms the starting point (0,0) into the point (–1,1), and it transforms steps up to steps to the right and vice versa. It thus defines a new path from (–1,1) to (n,m).

Because all such paths will have to cross the line y = x + 1 at some point, they all correspond to a line that starts at (0,0) and terminates at (n,m). As a consequence, the operation of conjugation creates a one-to-one map between the paths from (0,0) to (n,m) which touch the line and the paths from (–1,1) to (n,m).

In this way, the second problem is thus reduced to the first, and the number of paths touching the line turns out to be C(n + 1 + m – 1, m – 1) = C(n + 1 + m – 1, n + 1). If we divide this by the total number of paths and do a bit of cancellation of factorials, we find that the proportion of ballot counts that are at some point misleading is m/(n + 1).

Plugging in some of the extremes also gives the expected results: When n and m are roughly equal and very large, this proportion is very close to (and smaller than) one half; when the winning candidate leads by a very large number of votes, the proportion is very close to 0.

Of course, this trick in no ways hinges on the fact that the line crosses the y-axis at y = 1. In fact, Mohanty's construction only discusses the general case y = x – t, using negative integral values for t.

A Bit of Archeology

Mohanty refers, as it seems everybody in the field does, to a series of popular mathematics papers by Howard D. Grossman. The papers were published in Scripta Mathematica between 1946 and 1954 under the title "Fun with lattice points" (O the joys of being a mathematician).

And then the troubles begin — Scripta Mathematica has gone south, and I can't find copies of it online or in any of the university libraries I have access to.

Grossman himself apparently published many articles on "popular" mathematics (which later generations could then discover were in fact "serious" math in a cheerful wrapping).

However, he doesn't seem to have a Wikipedia page, and I don't know anything about him. In the papers that I do have access to, he is simply "Howard Grossman, New York City" or, more elaborately,

Howard D Grossman
100 La Salle Street, 13 B,
New York 27, New York, U.S.A.

OK, so apparently, he lived in Morningside Gardens, New York. This points in the direction of Columbia University, but the style and direction of his papers point in the direction of high school teaching. I don't know.