TALMUDIC LATTICE PATH COUNTING

Jane Friedman, Ira Gessel, and Doron Zeilberger

Appeared in : J. Comb. Theory, Ser. A 68(1994), 215-217.

Two are holding a talit, one is saying it is all his, and (the other) one is saying it is all his, ... let them each get half. (Bava Metzia)

Consider all planar walks, with positive unit steps (1, 0) and (0, 1), from the origin (0, 0) to a given point (a, b). Let L be the line joining the beginning to the end, i.e. the line bx − ay = 0. Call the region below L ”downtown”, and the region above L ”uptown”, the line L being the border-line between downtown and uptown. Each such walk has a + b − 1 points, not counting the endpoints. For i = 0, ..., a + b − 1, let W_{i} be the set of walks with ”exactly” i points downtown and ”exactly” a + b − 1 − i points uptown. How do we treat those walks that have some points on L? If there are i points downtown, and j points on L, then each of the sets W_{i}, W_{i+1}, ..., W_{i+j} have equal claim for this walk. If it is possible to divide a talit, then why not divide a walk. After the j + 1 contesting sets take oaths that they each own at least 1/(j + 1) of the contested walk, we declare that each gets exactly 1/(j + 1) of that walk. It turns out that this way of distributing border-line (sic!) walks is as fair as can be, since we have:

Theorem: The sets W_{i}, i = 0, ..., a + b − 1 are equi-numerous.

Since there are altogether (a + b)!/(a!b!) walks, it follows from the conjecture that each set boasts (a + b − 1)!/(a!b!) members. We need the following lemma, that is a slight extension of a result of Spitzer([3], Theorem 2.1, see also [2], Ch. 3 and [4], Ch. 8), and that generalizes the so-called ”cycle lemma” of Dvoretzky and MotzkinF [1].

Lemma: Let (r_{1}, ..., r_{n}) be a vector of real numbers that add up to zero. Then for each 1 <= i <= n, there exists exactly one (circular) shift (r_{j+1}, ..., r_{n}, r_{1}, ..., r_{j}) with the property that it has i partial sums that are positive, counting talmudically.

Proof of the Lemma: First assume that all the partial sums are distinct. If r_{1} + ... + r_{j} is the i + 1^{th} largest partial sum, then obviously (r_{j+1}, ..., r_{n}, r_{1}, ..., r_{j}) has exactly i partial sums that are positive, because the relative ranking of the partial sums is still the same, and there are i partial sums that are bigger than r_{1} + .. + r_{j}. Starting things at r_{j+1}, shifts that partial sum to be 0, and since there are i partial sums that are bigger, it means that there are i partial sums that are positive.

Now if there are ties, we let the partial sums share places. If there are j partial sums that share the i + 1, i + 2, ..., i + j places, then the corresponding j shifts will all have i positive partial sums, and

Department of Mathematics, University of San Diego, Alcala Park, San Diego, CA 92110; janef@teetot.acusd.edu.

Department of Mathematics, Brandeis University, Waltham, MA 02254; ira@cs.brandeis.edu. Supported in part by the NSF. Department of Mathematics, Temple University, Philadelphia, PA19122; zeilberg@euclid.math.temple.edu. Supported in part by the NSF. The third author grew up in Kiryat Motzkin, that was named after Theodore Motzkin’s father, Leo, the great Zionist leader. There are at least two other examples of Zionist leaders whose sons became combinatorialists: Ze’ev Jabotinsky, whose son Eri, was a professor of Mathematics at the Technion, and Alex Wilf, whose son is Herb Wilf. j partial sums that are 0. But, counting talmudically, this means that each one of these j shifts gets 1/j of each of the i + 1, ..., i + j places.

Proof of the Theorem: Let’s divide all the paths into equivalence classes, where a path is equivalent to all its circular shifts. We will show that the contributions coming from any equivalence class to each W_{i} is independent of i. Given any such path, consider the sequence obtained by replacing the step (1,0) by b, and the step (0, 1) by −a. By the lemma, all the circular shifts contribute equally to the W_{i}. Now, it may happen that not all the shifts of a path are distinct paths, but then it is easy to see that each path occurs with the same multiplicity, so the contribution to each of the W_{i} is still the same. QED

Acknowledgement: We thank Hank Krieger for raising this problem, and an anonymous referee for some very helpful suggestions.

Reference

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

2. F. Spitzer, A combinatorial lemma and its applications to probability, Trans. Amer. Math. Soc. 82(1956), 323-339.

3. S. G. Mohanty, ”Lattice Path Counting and Applications”, Academic Press.

4. L. Taka’cs, ”Combinatorial methods in the theory of Stochastic Processes”, J. Wiley.

Feb 1992 ; Revised June 1992.