1
$\begingroup$

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.

$\endgroup$
4
  • 2
    $\begingroup$ 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. $\endgroup$ Commented Jan 23, 2021 at 21:31
  • $\begingroup$ 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. $\endgroup$ Commented Jan 23, 2021 at 21:35
  • $\begingroup$ @RossMillikan i have updated, hopefully it clarifies, you can leave the B to D region, but you cant leave the overall grid. $\endgroup$
    – Lewis Trem
    Commented Jan 23, 2021 at 22:00
  • $\begingroup$ There is no known formula, and the problem is suspected to be computationally hard. See math.stackexchange.com/questions/1022245/… $\endgroup$ Commented Jan 24, 2021 at 18:35

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
-1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .