On a grid of m×n squares, how many ways exist to get from the top-left corner to the bottom-right corner if you can only move right or down on an edge?
This question confuses me in two ways, one from the solution of the answer and another from the method i chose, which is incorrect but i cannot see why.
The solution:
The number of ways to choose m rightward steps out of m+n total steps, such that you must travel m steps right and n steps down, is given by:
$$\binom{m+n}{m}=\frac{(m+n)!}{m!n!}$$
Since for each of these combinations, the remaining n steps down are uniquely determined, there is only 1 combination. Hence, the final answer is:
$$\binom{m+n}{m}=\frac{(m+n)!}{m!n!}$$
My question for this solution, instead of m+n total steps, isn't there m+n-2 total steps, since you need to transition between cells rather than the number of cells and that you start at the top-left.
My solution:
There are n-1 right moves, that need to be distributes across the grid. These right moves have to be distributed across the column lines at certain levels, of which there are m levels/rows.
therefore there is $$m^{n-1}$$, and removing the repeated orderings, there is $$\frac{m^{n-1}}{(n-1)!}$$.
For each possibility the down movements are also unique, so this is the final solution.
my solution is obviously wrong, but i don't understand why.
Any help will be greatly appreciated.
This question is from: https://openclimb.io/practice/p1/q13/
Best Answer
First of all, there should be $n$ right moves, not $n-1$. The confusion arises because there are two ways to move on an $m\times n$ grid of squares; you can either move on the squares themselves, or along the vertices. Since the correct answer is $\binom{m+n}m$, the correct interpretation must be the vertices, so there are $n$ right moves. Similarly, each right move can occur at one of $m+1$ possible heights, not $m$.
This transforms your answer into $$ \frac{(m+1)^n}{n!}, $$ but this is still incorrect, for a more subtle reason. The problem is that there are sometimes fewer than $n!$ unique rearrangements of a given placement of the $n$ horizontal edges. If you have multiple edges at the same height, then some of the $n!$ permutations are redundant, meaning you cannot divide by $n!$.
Maybe it would help to look at a small case, say $m=1$ and $n=2$. There are $(m+1)^n=4$ ways to distribute the two horizontal edges. You can do
high, high,
low, low,
high, low, and
low, high.
The last two methods, (high, low) and (low, high), are permuted versions of each other, and form a class of size $2!$. That is OK. However, when you permute (high, high), the result is still (high, high), even if the permutation is nontrivial. Therefore, the group associated with (high, high) only has size one, not $2!$. Since the groups are not uniformly sized at $2!$, you cannot count their number by dividing by $2!$.