Counting pairs of lattice paths by intersections

Abstract

On an $r\times (n-r)$ lattice rectangle, we first consider walks that begin at the SW corner, proceed with unit steps in either of the directions E or N, and terminate at the NE corner of the rectangle. For each integer $k$ we ask for $N_k^{n,r}$, the number of {\em ordered\/} pairs of these walks that intersect in exactly $k$ points. The number of points in the intersection of two such walks is defined as the cardinality of the intersection of their two sets of vertices, excluding the initial and terminal vertices. We find two explicit formulas for the numbers $N_k^{n,r}$. Next we note that $N_1^{n,r}=2N_0^{n,r}$, i.e., that {\em exactly twice as many pairs of walks have a single intersection as have no intersection\/}. Such a relationship clearly merits a bijective proof, and we supply one. We discuss a number of related results for different assumptions on the two walks. We find the probability that two independent walkers on a given lattice rectangle do not meet. In this situation, the walkers start at the two points $(a,b+x+1)$ and (a+x+1,b)$inthefirstquadrant,andwalkWestorSouthateachstep,exceptthatwhenawalkerreachesthe$x$-axis(resp.the$y$-axis)thenallfuturestepsareconstrainedtobeSouth(resp.West)untiltheoriginisreached.Wefindthatiftheprobability$p(i,j)$thatastepfrom$(i,j)$willgoWestdependsonlyon$i+j$,thentheprobabiltythatthetwowalkersdonotmeetuntiltheyreachtheoriginisthesameastheprobabilitythatasingle(unconstrained)walkerwhostartsat$(a, b+x+1)$andandtakes$a+b+x$steps,finishesatoneofthepoints$(0,1), (-1,2), \ldots, (-x,1+x)$.

10 pages