a 20x20 grid will be traversed in a lot of way. But each way is composed of 40 simple actions
_simple_action_DOWN: from current point move one step down (1 unit)
_simple_action_LEFT: from current point move one step left (1 unit)
So the question is equivalent to: given 40 indexes place 20 DOWN and 20 LEFT on them
Meaning given 40 indexex that are all DOWN , chose 20 random ones and palce LEFT on them. meaning Combinations of 40 taken by 20.
Same generalization for a rectangle of sizes L and l : given L+l position , choose randomly L of them = Combinations of (L+l) taken by l
Sorry for the English , not my native language.
posted 8 years ago
Ok, how about this variation:
How many ways are there to get from (0,0) to (20,20) (in the lower right quadrant, for the sake of discussion) if you're allowed to backtrack at most once? i.e. You're allowed one step to the left or one step up, but not both.