[Math] Path counting in a grid – what’s the way to prove this approach

combinatoricsdiscrete mathematicsproof-writing

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

  1. down
  2. down
  3. right
  4. right
  5. 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

  1. down 1
  2. down 2
  3. right 1
  4. right 2
  5. 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)! \div (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? But my question question is, what is $n$ in this case (steps? grid size?) if I would like to write a proof for this? Or is induction not possible in this case?

Best Answer

Maybe this example meets your need.

Suppose that $3$ from the numbers in $\{1,\dots,5\}$ must be selected.

We can start with writing the numbers in all possible orders, and then pick the $3$ utmost left as the selected ones. There are $5!=120$ orders and we get something like:

  • 123|45
  • 123|54
  • ...
  • 543|21

Now observe that the e.g. the orders 12345 and 12354 both result in the selection 123. Now wonder how many orders can be found that result in selection 123. For the order of numbers 1,2,3 there are $3!=6$ possibilities and for the order of the numbers 4,5 there are $2!=2$ possibilities. That means that the selection 123 is the result of $3!2!$ of the $5!$ arrangements. To repair this overcounting we divide by $3!2!$ and we end up with $\frac{5!}{3!2!}$ distinct selections.

Related Question