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.

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

  2. 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 an 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)\).

Note by Le Anh
4 months, 2 weeks ago

No vote yet
1 vote

  Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link]( link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 \( 2 \times 3 \)
2^{34} \( 2^{34} \)
a_{i-1} \( a_{i-1} \)
\frac{2}{3} \( \frac{2}{3} \)
\sqrt{2} \( \sqrt{2} \)
\sum_{i=1}^3 \( \sum_{i=1}^3 \)
\sin \theta \( \sin \theta \)
\boxed{123} \( \boxed{123} \)


Sort by:

Top Newest

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

Upper bounds:

  • There are \( (n \cdot m)! \) different ways to reach all points but many of them aren't allowed.
  • There are at most \( (n+1) \cdot (m+1) - 1 \) steps to make and every step can go to four directions, so there are at most \( 4^{(n+1) \cdot (m+1) - 1} \) different ways.

Lower bounds:

  • As you mentioned, there are \( \binom {n+m}{m} \) shortest paths.
  • You could start categorizing the paths and calculating their numbers, but I don't really think that these bounds say very much. The upper bounds grow so much faster that the difference becomes far too big.

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

Henry U - 4 months, 2 weeks ago

Log in to reply

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

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

Henry U - 4 months, 2 weeks ago

Log in to reply

I'm thinking of creating an algo to find all possible ways then we can form a conjecture about this.

Le Anh - 3 months, 2 weeks ago

Log in to reply

@Le Anh This is a good way! Let me know about the results. Thanks!

Henry U - 3 months, 2 weeks ago

Log in to reply

Just resurrecting this question - it seems very interesting! Did you manage to get any numerical data? There's one point that seems slightly ambiguous. What exactly counts as a path? Is it the collection of edges that are traversed, or is it the order that the points are visited in?

As an example of what I mean, in the diagram you provided, you could visit the points in the order \((0,0),(0,2),(3,2),(3,1),(1,1),(1,0),(2,0),(2,3),\ldots\), or you could visit them in the order \((0,0),(0,2),(2,2),(2,0),(1,0),(1,1),(3,1),(3,2),(2,2),(2,3),\ldots)\). Both use the same edges, and obey the rules, but are they the same path? (I'll try to upload a diagram, not quite sure how to do it in comments)

Some general thoughts:

  • if there are \(E\) edges in total, there are \(2^E\) possible sets of edges that are used in the path. You can work out if any particular set of edges works by checking the degrees of the all the vertices; the bottom-left and top-right vertices must have degree \(1\), and all others must have even degree. (Note that if the order in which the edges are traversed matters, this approach is not all that helpful. Also, \(2^E\) grows very quickly with the size of the grid. Might still be useful for small grids, though)

  • if the order of the edges matters, a recursive search algorithm might be a good way to go. You can store "used" edges, and terminate the algorithm when the top-right point is reached, or when there are no available edges. Again, the number of possible paths grows quickly, but it could be useful for getting some numerical data together.

Let me know if this is still of interest to you (or if you managed to find a solution!)

Chris Lewis - 1 month, 3 weeks ago

Log in to reply

Hi Chris, let us say the path would be the collection of edges. So the two ways of visiting the points you stated would be considered as one "path" (since I think the other way around would be more complicated). Unfortunately I haven't managed to find a solution. Your second comment is really worth a try.

Le Anh - 1 month, 2 weeks ago

Log in to reply

Liposomes constituted from light-sensitive lipids have been explored since early 1980s. Membrane permeabilization of these light-controlled liposomes are induced upon light exposure of specific wavelength to target drug release. A successful example of photo-activated liposome formulation in clinical use now is Visudyne therapy to treat age-related macular degeneration of (AMD) in patients.

Creative Biostructure - 1 month, 4 weeks ago

Log in to reply

Plasmids were identified initially as elements carrying extrachromosomal genetic information of Escherichia coli (E. coli) [1]. Nowadays, these typically circular DNA molecules have become one of the most important tools in genetics and molecular biology.

Wendy Wilson - 1 week, 5 days ago

Log in to reply

Green fluorescence protein (GFP) is a 27 kDa protein derived from the jellyfish Aequorea victoria, which emits green light (emission peak at a wavelenth of 509 nm) when excited by blue light (excitation peak at a wavelenth of 395 nm). GFP has become an invaluable tool in cell biology research, since its intrinsic fluorescence can be visualized in living cells.

Wendy Wilson - 1 month, 4 weeks ago

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:

Anton Goetze - 4 months, 2 weeks ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...