My house is located at $(0,0)$ and the supermarket is located at $(7,5)$. I can only move in the upwards or in rightward directions. How many different routes are there? Obviously, ${12}\choose{7}$ $=$ ${12}\choose{5}$ $=$ $792$. How many paths are there if I want to avoid the really busy intersection located at $(3,3)$?
I have three ideas, all of which lead to different answers:
1) My first idea was to label out the grid and write the number at each intersection that represents how many paths cross that point. This was equivalent to writing out pascals triangle in a tilted diagonal way, until I reached $(3,3)$ whereI had to write a $0$, but then I proceeded as you'd expect, the intersection's number was equal to the one below it added to the one to the left of it. At $(7,5)$ I ended up getting $490$.
After this, I wanted a combinatorial way to confirm my answer, so I tried:
2)counting all the paths from $(0,0)$ to $(3,3)$ and subtracting those away from $792$. So here I would subtract ${6}\choose{3}$ $=20$.
3)counting all the paths from $(3,3)$ to $(7,5)$ and subtracting those away from $792$. So here I would subtract ${6}\choose{4}$ $=15$.
So my question is: which method of thinking is correct and why do the other two not lead to the correct answer (what do they over/under count)? I suspect that my first try was correct, and the answer is $490$, but I don't see the algorithmic way of seeing it…
EDIT: Made a correction to my grid. I wrote a $34$ instead of a $36$ for the intersection at $(7,2)$. Woops!
Best Answer
You need to look at the complement, which is all the paths from $(0,0)$ to $(7,5)$ that pass through $(3,3)$.
As you noted, the number of paths from $(0,0)$ to $(3,3)$ is ${6\choose3} = 20$, and the number of paths from $(3,3)$ to $(7,5)$ is ${6\choose4} = 15$. So the number of paths from $(0,0)$ to $(7,5)$ that pass through $(3,3)$ is all combinations of the above paths, which means $20\cdot15=300$ paths.
$792-300=492$, and so $492$ is the final answer.