Thought Process

In an n by n grid what must we do to get from the top left to bottom right? We need to move n units to the right and n units down, so in a 20 by 20 grid our path MUST be 40 units long consisting of 20 movements to the right and 20 movements down

I'm sure most of you have heard of Permutations of Indistinguishable Objects but if you haven't I will give you an example:

Consider the word SUCCESS, the question is, how many unique ways can we order these letters?

One example is SCCESSU, another may be SCUCESS, but what if we lets say swap the 2 C's, then SUCCESS is a permutation of SUCCESS? Technically speaking yes, but it is not unique!

Consider 7 empty slots _ _ _ _ _ _ _ ,obviously if we are not talking about unique ways to place the 7 letters of SUCCESS, then there are 7! (! denotes factorial) ways to order them, but we will have duplicates because there are 2 C's and 3 S's

To combat this, notice that given any string of letters say, SSSEUCC, there are 3! ways to order the S's and 2! ways to order the C's, this means this one string will appear 3!*2! = 12 times in the overall number of permutations, and this is the same for every single string. Therefore, take every string (There are 7! of them) and divide by 3!*2! to remove the 11 duplicates!

Our final formula for number of unique permutations for the word SUCCESS is 7!/(3!*2!) = 420

Now back to the problem, lets rephrase it with our new knowledge:

Consider a string with 20 R's and 20 D's (where R, D represent right or down movement respectively), each string represents a path from top right to bottom left on the board, how many unique strings (and this means paths) can we make?

Well there are 40 letters in total and we have 20 R's and 20 D's therefore by the reasoning above there will be 40!/(20!*20!) different ways to uniquely order the string!

Try to come up with a general formula for an n by n and n by m grid!