Combinations/Permutations Count Paths Through Grid

Question

I am curious about a situation in permutations/combinations. This question stems from a challenge site (project euler, problem 15) and research found on this exchange and elsewhere. The question involves finding a path through a 20 x 20 grid from one corner to another. This question has been generally addressed previously here: Counting number of moves on a grid

But I am curious about the solution and was hoping to understand it further. The use of the algorithms for combinations and permutations makes sense to me. This problem can be though of by simplifying it to the fact there will always be 40 total moves, 20 of which will be down and 20 of which will be right to reach a valid end point. The solution involves using the algorithm for combinations, i.e. 40C20. Reading the responses it has been stated that order does not matter and as such this is a combination. However, traditionally I would think this would call for a permutation because although starting as (0,0) and going Right-Down or Down-Right both gets you to (1,1) they do so using different paths and I would think would need to be counted as unique. However, this does not appear to be the case. If thought of in terms of strings such as RRRRDDDD... for the series of moves, does not each unique position of an R and a D matter? Thanks for any help, I like to understand the concepts behind a problems solution before I move on, any additional explanation would be much appreciated.

Answer 1

As you stated, any path is a sequence of moves to the right or down, hence a word of length $40$ written only with letters $R$ and $D$, where there are $20$ of $R$ and $20$ of $D$, so the solution to this problem is the number of such words. This can be computed using either combinations (without repetition) or permutations with repetition:

• using combinations, the answer is $\dbinom{40}{20}$ since any word with $20$ of $R$ and $20$ of $D$ is uniquely defined by the positions where we write $R$ ($D$ is written in the remaining positions), so we need to choose $20$ numbers from the set $\{1,2,3,\ldots,40\}$ which indicate the positions of $R$ in the word.

• using permutations with repetition, the answer is $\dbinom{40}{20,20}% =\frac{40!}{20!20!}=\dbinom{40}{20}$. This is the number of ways that $20$ of $R$ and $20$ of $D$ can be permuted in a word. In general, if we have a word with $n$ letters, of which $n_{1}$ represent the same letter $L_{1}$, $n_{2}$ represent the letter $L_{2}$, and so on, $\ldots, n_{k}$ represent the letter $L_{k}$ ($n=n_{1}+n_{2}+\ldots+n_{k}$), then the number of ways you can permute the letters of the word is the number $$ \dbinom{n}{n_{1},n_{2},\ldots,n_{k}}=\frac{n!}{n_{1}!n_{2}!\cdots n_{k}!}. $$

Answer 2

You might also like to note that the use of combinations in lieu of permutaions is convenient only for a binomial situation, and for a multinomial situation, eg for a similar problem on a grid with more than 2 dimensions, it is simpler to use permutations.

note: edited in view of comments below by digital Ink