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
-
-
-
You want a combination. To take a trivial case to move 3 blocks east and 0 blocks north, there's just 1 way, even through 3!=6.
Thanks. Twitter will use this to make your timeline better. UndoUndo
-
-
-
Yep. All this follows neatly from the same logic by which Pascal's Triangle enumerates binomial coefficients. https://en.wikipedia.org/wiki/Binomial_coefficient …
-
By S(a,b), denote the number of shortest paths from (0,0) to (a,b), for a,b >= 0. S(x,0) = S(0,y) = 1. If x,y > 0 , S(x,y) = S(x-1,y) + S(x,y-1). So, looking at an actual grid, you can fill in # of paths through each point, iterating really quickly.
- 6 more replies
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 -
-
-
nah, it's a question of permuting a list of N identical L-choices and M identical R-choices, so you have (N+M)! total orderings and then a factor of N! redundant orderings for the identical Ls and a factor of M! redundant orderings for the Rs
-
Yes, the formula has to be symmetric in M and N so the Kshitij's formula is wrong by inspection :D
End of conversation
New conversation -
-
-
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?
- 1 more reply
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.