1

I was reading about a the derivation of the formula for the number of paths from one corner to another corner of a H by W grid here and I wondered whether it is possible to apply the result: $\binom{(H-1)(W-1)}{H-1}$ to find the number of paths from a given square on the top row of the grid to another selected square in the bottom row. enter image description here

For example the number of paths from B to J. I thought of reducing the grid to just the columns B to D, counting the paths there and then adding the possible paths from every other square outside the reduced grid. However I had trouble in finding a formula for the possible paths from outside of the reduced grid.

In a path you cant repeat a square, and you can move to any adjacent square.

Lewis Trem
  • 241
  • 1
  • 10
  • 2
    What are the rules regarding what path you can take? Are you allowed to go out of the B to D region? Are you allowed to go horizontally as much as you like? Without the rules there is no answer. – Ross Millikan Jan 23 '21 at 21:31
  • The comment of @RossMillikan beat me to the punch; clarification is needed. One approach is to specify that when going from $B$ to $D$, you can never move upward. However, as Ross Millikan's comment indicates, this is still insufficient, because you could go left and right indefinitely. – user2661923 Jan 23 '21 at 21:35
  • @RossMillikan i have updated, hopefully it clarifies, you can leave the B to D region, but you cant leave the overall grid. – Lewis Trem Jan 23 '21 at 22:00
  • There is no known formula, and the problem is suspected to be computationally hard. See https://math.stackexchange.com/questions/1022245/number-of-self-avoiding-rook-walks-in-a-rectangular-grid – Mike Earnest Jan 24 '21 at 18:35

2 Answers2

1

A possible (but involved) approach

You could represent moves by complex numbers:

$1$ is move right, $-1$ is move left, $i$ is move up, $-i$ is move down.

Then a path is a sequence such as $1,-i, -1, ...$

The conditions for a valid path then have simple arithmetical equivalences.

To move from B to J The total sum of the numbers must be $2-5i$.

To stay in the grid For any natural number $n$, the sum $S_n$ of the first $n$ numbers must satisfy $4\ge \Re (S_n)\ge -1, 0\ge \Im (S_n)\ge -5. $

To not visit any square twice No sum of successive numbers must have sum $0$.

This looks suitable to be programmed if that is of interest.

-1

In the original source, note that each step in the path was Right or Down. With those rules, any path from B to J requires 2 Rights and 5 Downs, in any order. There are $\binom{5+2}{2} = 21$ such paths. But to go from B to G, say, you would need Left and Down moves. If you allow Left and Right both, then the number of paths is infinite, as you could move Right Left Right Left... as long as you like.

Edit: With the restriction about not visiting a position more than once, the number of paths with every direction allowed is finite but large (compared to the board size). For instance, the number of paths between opposite corners of a $2 \times n$ grid is $2^{n-1}$, already exponential.

Brian Hopkins
  • 2,257