Combinations/Permutations Count Paths Through Grid

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.

-

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}!}.$$

-
Thank you, this was a very helpful explanation and cleared up my confusion! – majic bunnie Jan 14 '12 at 0:34

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

-
Actually, this is not true. You can still solve the problem in any dimension using only combinations, if you don't know permutations with repetitions. This is the same with proving the formula $$\dbinom{n}{n_{1},n_{2},\ldots,n_{k}}=\frac{n!}{n_{1}!n_{2}!\cdots n_{k}!}$$ using combinations: first choose the positions of letter $L_{1}$ (this can be done in $\dbinom{n}{n_{1}}$ ways), then choose the position of letter $L_{2}$ (in $\dbinom{n-n_{1}}{n_{2}}$ ways), and so on until you arrive to letters $L_{k}$ which are put in only one way , in the remaining positions. – digital-Ink Jan 14 '12 at 18:02
(continued from previous comment) Finally you get $$\dbinom{n}{n_{1},n_{2},\ldots,n_{k}}=\dbinom{n}{n_{1}}\dbinom{n-n_{1}}{n_{2}% }\dbinom{n-n_{1}-n_{2}}{n_{3}}\cdots\dbinom{n-n_{1}-n_{2}-\ldots-n_{k-2}% }{n_{k-1}}=\frac{n!}{n_{1}!n_{2}!\cdots n_{k}!}.$$ The same argument applies when the letters are actually directions. – digital-Ink Jan 14 '12 at 18:04