Project Euler #15 - Math

Question:

Starting in the top left corner of a 22 grid, there are 6 routes (without backtracking) to the bottom right corner.

How many routes are there through a 2020 grid?

Solution:

I spent a LONG time trying to figure out how this 2x2 grid has 6 unique routes fact was relevant to the solution of this problem. I sat down, drew the diagram out on a piece of paper, and racked my brain for a good hour trying to find some link between 2x2 = 6 and 20x20 = ? 


Then, I walked away, had lunch, and then sat back down to tackle this problem again. Then a fact just jumped out at me: THIS IS EASY! I spent an hour looking in the wrong direction when this is really just a simple math problem. In fact, I didn't even code a solution. 


There is one important fact to realize: It takes 20 moves to the right, and 20 moves down to get to the end point no matter which route you decide to take. So really the only thing that matters is when you decide to make a right turn and when you decide to make a down turn. All in all, there are 40 moves required to get to the end point no matter which route you chose (again... 20 right, 20 down). So this is just a combinations problem! 


Picture it like this:
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
(40 blank spaces)


How many ways are there to place 20 "D"s in the 40 blank spaces. 


Once the 20 "D"s are placed, the rest of the blank spaces get filled with "R"s and you achieve a sequence of "R"s and "D"s that will lead to the end point every time (doubt me? try it!). 


Mathematically, this is represented as "n  choose k", where n is the number of spaces and 
k the number of "D"s. The equation is: 


n!/( n! * (n-k)! )


Substituting in the values 40 for n, and 20 for k:


40! / (20! * 20!)


Now, factor and get the answer! ... or just use your calculator!