I was recently watching a video on Khan academy,
where he works through a problem about finding all possible paths in an n X n grid from the top left position to the bottom right position, by only going down or right.
Basically the approach he takes is based on using pascals triangle and counting the ways to reach at a certain position and add them to the number of ways so far.
I got interested in this and tried to generalize a formula for finding the amount of possible paths in a n X m grid.
My idea is as follows: Let's assume a 2 x 3 grid. We start at the top left and need to go to the bottom right (assuming we can only move right/dow). One possible path would be
down down right right right As it turns out, all possible paths in a 2 x 3 grid will have a length of n + m = 5 in this case.
If we see moving through the grid as a kind of series of commands (down/right), we can find all possible permutations of down/right by computing (n+m)! For example, in the 2 x 3 grid we compute 5!, that would give us all possible permutations of
down 1 down 2 right 1 right 2 right 3 However, that would also count down2, down1, ... as valid combination, which it's not, you can go at most 2 times down, but you must start with down1 from the start position. The refined formula looks like this (to get unique combinations of commands):
(n+m)!รท(n!m!)
In a quadratic 5 x 5 grid, the above would evaluate to 252, in a 2 x 3 grid it would be 10 paths. From what I can see, that seems like a correct approach, at least from a few examples I tried.
My next step was to try to write a proof for this, I thought maybe a proof by induction would be possible? if I would like to write a proof by induction for this how can I?
