Counting paths across a semi-infinite grid

May 22nd, 2008 ~ Posted in: Mathematics

Let’s assume you’re walking across a cobblestone pavement laid out in an m \times \infty grid. You’re currently standing on point (m,b) and you want to make your way to point (0,t)

pickup pencircle scaled 2; for i=0 upto 10: draw (-2cm, i*cm)--( 12cm, i*cm); endfor for j=-1 upto 11: draw (j*cm,0)--(j*cm,10cm); endfor dotlabel.lrt(btex $(m,b)$ etex, (7cm, 0)); dotlabel.ulft(btex $(0,t)$ etex, (3cm, 10cm));

while constraining yourself to moving up a step at a time, either straight up, to the left, or to the right. Assume |t-b| < = m, how many such paths go from your starting point to your destination?

Note that each path is identical to a m tuple of ones, negative ones, and zeros, with the constraint that the sum of the tuple should be t-b so what we’re looking for is the number of all such tuples. Let R,L,Z be respectively the number of ones, negative ones, and zeros in a tuple, then we can solve for L,Z in terms of R: L = R + b - t, Z = m - 2R - b + t.

Let R_{\text{min}}, R_{\text{max}} be respectively the minimum number of moves to the right, and the maximum number of moves to the right you can take in any allowable path from your origin to your destination; using multinomial coefficients, the number of paths is given by

\displaystyle \sum_{R = R_{\text{min}}}^{R_{\text{max}}} \left({ m \atop L; R; Z} \right).

Clearly R_{\text{min}} = \max\{0, t-b\}, but determining R_{\text{max}} is a little trickier. To find it, note that t - b \equiv R - L \mod 2 and m - Z \equiv R + L \mod 2, so Z \equiv t - b + m \mod 2 . This gives two equations for R_{\text{max}}: L + R_{\text{max}} + {(t - b + m) \mod 2} = m and t - b = R_{\text{max}} - L ; solving them gives R_{\text{max}} = \frac{m - b + t - {(m - b + t)\mod 2}}{2}. Putting it all together, the number of paths is

\displaystyle \sum_{R = \max\{0, t-b\}}^{\frac{m - b + t - {(m - b + t)\mod 2}}{2}} \left({ m \atop R + b - t; R; m-2R-b+t} \right)

A much harder problem would be to attempt this for a m \times n grid, because (in a combinatorial approach like this) you would only count the tuples where consecutive stretches of moves to either the left or right are not excessively long. I suspect it would be more productive to find a probabilistic approach in that case.

Mathematics ~

This entry was posted on Thursday, May 22nd, 2008 at 11:19 pm and is filed under Mathematics. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

Leave a Reply