Number of Paths on a Grid From S to M

Question

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.

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.

Answer 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.

Answer 2

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.