%begin macros
\parskip=8pt
\magnification=\magstephalf
\parindent=0pt
\overfullrule=0in
%end macros
\rm
{\bf TALMUDIC LATTICE PATH COUNTING}

{\it Jane Friedman, Ira Gessel, \rm
  and \it
Doron Zeilberger}

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

\footnote{}{
Department of Mathematics, University of San Diego, Alcala Park, San
Diego, CA 92110; janef@teetot.acusd.edu.
}
\footnote{}{
Department of Mathematics, Brandeis University, Waltham, MA 02254;
ira@cs.brandeis.edu. Supported in part by the NSF.
}
\footnote{}{
Department of Mathematics, Temple University,
Philadelphia, PA19122; zeilberg@euclid.math.temple.edu.
Supported in part by the NSF.
}

\it
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)
\rm

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 {\it 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 {\it 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:

{\bf 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 Motzkin\*F 
\footnote{}{
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.
}
[1].

{\bf 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.

{\bf 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 $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.

{\bf 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

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

{\bf Reference}

1. A. Dvoretzky and Th. Motzkin, \it
A problem of
arrangements\rm
 , Duke Math. J. {\bf 14} (1947), 305-313.

2. F. Spitzer, \it
A combinatorial lemma and its applications to
probability\rm
, Trans. Amer. Math. Soc. {\bf 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.
\end
