Given a $10\times10$ grid (each axis enumeration is $0,1,2,..,9$) a grid walk is started at point $(0,0)$ and finished at point $(9,9)$. Each move can be either to the right or up. How many paths are possible if points $(3,3), (6,3), (6,6)$ must not be crossed?
I know that the total number of possible paths is ${9+9\choose 9} = 48620$.
Inclusions/exclusion principle can be used. $(6,3)$ can be visited in: $$ {6+3\choose 3}{9+9-(6+3)\choose 9-3}=7056 $$ Similar calculations can be made for the other two points. Where I'm having trouble is calculating crossing of $2$ and $3$ points simultaneously. How do I do that?
If a path passes through $(3,3)$ and then $(6,3)$, it must travel only horizontally from $(3,3)$ to $(6,3)$. This gives us $$\binom{3+3}{3}\cdot 1\cdot \binom{9+9-6-3}{9-3}$$ total paths, where the first binomial coefficient is the number of walks from $(0,0)$ to $(3,3)$, the $1$ is the number of walks from $(3,3)$ to $(6,3)$, and the second binomial coefficient is the number of walks from $(6,3)$ to $(9,9)$.
If a path passes through $(3,3)$ and then $(6,6)$, we will have $$\binom{3+3}{3}\cdot \binom{6+6-3-3}{6-3} \cdot \binom{9+9-6-6}{9-6}$$ Where the first coefficient counts paths from $(0,0)$ to $(3,3)$, the second counts paths from $(3,3)$ to $(6,6)$, and the third counts paths from $(6,6)$ to $(9,9)$.
Using these two examples, you can calculate the number of paths passing through $(6,3)$ and $(6,6)$.
Now we must count the number of paths going through all three. First, the walk must pass through $(3,3)$, which can be done in this many ways: $$\binom{3+3}{3}$$ Then it must pass through $(6,3)$, which can only be done $1$ way (by going horizontally). Then it must go through $(6,6)$, which can be done only $1$ way (by going vertically). Then, from $(6,6)$ to $(9,9)$, we have $$\binom{9+9-6-6}{9-6}$$ Which gives us a total of $$\binom{3+3}{3}\cdot 1\cdot 1\cdot \binom{9+9-6-6}{9-6}$$ Now, after calculating these binomial coefficients, you can do your inclusion-exclusion!