No. of grid walks not going through four points

combinatoricsinclusion-exclusion

Given a $11\times11$ grid, and a grid walk is starts at point $(0,0)$ and finishes at the point $(10,10)$. The coordinates of each move are non-decreasing (i.e., you can either move right or up only). How many paths are possible if points $(3,3), (7,2), (3,7),(7,7)$ must not be crossed?

I already know that the total number of possible paths without any restrictions are ${10+10\choose 10}$. So, I need to figure out the no. of bad paths that need to get subtracted from ${10+10\choose 10}$. It is fairly straightforward to calculate the paths that need to avoid any of the four points by finding the complement of the paths that pass through one of the points. For example, $(3,3)$ can be visited in ${3+3\choose 3}{10+10-(3+3)\choose 9-3}$ ways.

However, I am facing troubles calculating the bad paths crossing through a combination of points simultaneously. How would I do that?

Best Answer

An alternative to inclusion-exclusion is to use recursion. Let $p(x,y)$ be the number of such paths from $(0,0)$ to $(x,y)$. By considering the last step into $(x,y)$, we find that $$p(x,y)=p(x-1,y)+p(x,y-1),$$ where $p(x,y)=0$ if $x<0$, $y<0$, or $(x,y)$ is blocked. The boundary condition is $p(0,0)=1$, and you want to compute $p(10,10)$.

\begin{matrix} 1 &11 &66 &166 &441 &1283 &3608 &7416 &14410 &29078 &\color{red}{60256} \\ 1 &10 &55 &100 &275 &842 &2325 &3808 &6994 &14668 &31178 \\ 1 &9 &45 &45 &175 &567 &1483 &1483 &3186 &7674 &16510 \\ 1 &8 &36 &0 &130 &392 &916 &0 &1703 &4488 &8836 \\ 1 &7 &28 &64 &130 &262 &524 &980 &1703 &2785 &4348 \\ 1 &6 &21 &36 &66 &132 &262 &456 &723 &1082 &1563 \\ 1 &5 &15 &15 &30 &66 &130 &194 &267 &359 &481 \\ 1 &4 &10 &0 &15 &36 &64 &64 &73 &92 &122 \\ 1 &3 &6 &10 &15 &21 &28 &0 &9 &19 &30 \\ 1 &2 &3 &4 &5 &6 &7 &8 &9 &10 &11 \\ 1 &1 &1 &1 &1 &1 &1 &1 &1 &1 &1 \\ \end{matrix}

Related Question