Is there an easy algorithm to
a) count the number of equivalent shortest paths on a manhattan grid
b) enumerate them systematically?
I wrote a dumb random algo and I could run it for a long time to count unique paths but I imagine there's a closed-form solution?
Conversation
Replying to
Yep. All this follows neatly from the same logic by which Pascal's Triangle enumerates binomial coefficients. en.wikipedia.org/wiki/Binomial_
2
3
A shortest path in an n by k grid is a sequence of length n+k of steps that are either "North" or "East". So the subset of steps that are "North" completely determines the path.


