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

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

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

Log in to reply

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!)

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.

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.

https://www.creative-biostructure.com/Photo-activated-Liposomes-Production-613.htm

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.

https://www.creative-biogene.com/Services/GMP-grade-plasmid-DNA-production-service.html

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.

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