Given an \(m \times n\) grid, it is easy to count the total number of shortest routes from the bottom left corner to the top right corner, since every move would be either upward or rightward. However, if we remove the restriction of "shortest" and instead use the restriction that "we can repeat vertices but not edges" (to prevent the case of infinite looping), how do we count the total number of routes? The new problem looks something like this: "Given an \(m \times n\) grid, how many routes are there to travel from bottom left corner to top right corner, whereby for every route we can repeat vertices but not edges?" Let the total number of routes be \(P(m,n) \). I tried two approaches which are used to solve the original problem. Both did not work.

In the original problem each shortest route has \(m+n\) steps. We have to choose \(m\) steps rightwards from the total of \(m+n\) steps, so the total number is the number of ways to arrange \(m\) step \(m+n\) positions, ie. \(\displaystyle \binom{m+n}{m}\). However, for the new problem, the steps can be up, down, left or right, and the total number of steps is not fixed. So I got stuck.

Recurrence Approach: Assign coordinates to the grid with the bottom left being \((0,0)\) and the top right being \((m,n)\). To reach point \((m,n)\) we must go from either point \((m-1,n)\) or \((m,n-1)\). I was considering if the total number of routes to \((m,n)\) could be reduced to a recurrence relation in that way: \(P(m,n)=P(m-1,n)+P(m,n-1)\) But then I realised that some routes can go to \((m-1,n)\) and then go to \((m,n-1)\) before reaching \((m,n)\) and vice versa, so there could be a overcount. Furthermore, the number of ways to move from \((0,0)\) to \((m-1,n)\) is actually more than \(P(m-1,n)\) since the extra column in the \(m\times n\) grid allows routes that move through there. Likewise for \(P(m,n-1)\).

No vote yet

1 vote

×

Problem Loading...

Note Loading...

Set Loading...

Easy Math Editor

`*italics*`

or`_italics_`

italics`**bold**`

or`__bold__`

boldNote: you must add a full line of space before and after lists for them to show up correctlyparagraph 1

paragraph 2

`[example link](https://brilliant.org)`

`> This is a quote`

Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.`2 \times 3`

`2^{34}`

`a_{i-1}`

`\frac{2}{3}`

`\sqrt{2}`

`\sum_{i=1}^3`

`\sin \theta`

`\boxed{123}`

## Comments

Sort by:

TopNewestI don't think there is a direct formula for this. You could start to calculate lower and upper bounds, for example

Upper bounds:

Lower bounds:

Maybe you should think about square grids first, or \( 1 \times n\), then \( 2 \times n \) and so on.

Log in to reply

\( 1 \times n\): \( n+1 \)

\( 2 \times n \): \( \binom {n+2}{2} \) shortest paths \( + ... \) I give up...

Log in to reply

This are very good questions and I think this is very hard to solve. Maybe you take a look at this website: https://www.adpoint.de/adwords-agentur/

Log in to reply