I'm actually interested in a second-order problem: count the fraction of paths that go through a particular segment. If you walked to work on a manhattan grid everyday, making random choices, how long before you walked a specific block? A specific sequence of blocks?
-
-
Show this threadThanks. Twitter will use this to make your timeline better. UndoUndo
-
-
-
all equivalent shortest paths have N x-steps and M y-steps, which you can take in any order, so i think it's just (N+M)!/N!M!
-
Ah ok, that's the formula I derived, but wasn't entirely sure of my logic, thanks... any idea how to enumerate them systematically?
- Show replies
New conversation -
-
-
Feels like N! ways.. so that would explode as N increases.
-
Enumerating them can be done recursively, but that will explode in running time.
End of conversation
New conversation -
-
-
The concept of betweenness centrality is kinda relevant to that https://en.m.wikipedia.org/wiki/Betweenness_centrality …
-
heh looks like I'm empircally rediscovering thathttps://twitter.com/vgr/status/1178027742467481600 …
End of conversation
New conversation -
-
-
Yep. All this follows neatly from the same logic by which Pascal's Triangle enumerates binomial coefficients. https://en.wikipedia.org/wiki/Binomial_coefficient …
-
how would I use pascal's triangle for enumeration here?
- Show replies
New conversation -
-
-
so the key idea is this: When considering the possible paths (tracing them out with your finger), you might whisper "Up, right, up, right...". [...] Using the text interpretation, the question becomes "How many ways can we re-arrange the letters rrrrrruuuu?"
End of conversation
New conversation
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.