No. of grid walks not going through four points

Question

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?

Answer 1

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}

Answer 2

You are right : without restrictions, the answer is $\binom{20}{10}$.

Now, we wish to count the bad paths, those that pass through at least one of $P=(3,3), Q=(7,2),R=(3,7), S=(7,7)$. Let us call $B$ as the set of bad paths, which pass through at least one of these points.

Let us call $B_P,B_Q,B_R,B_S$ to be the sets of paths passing through $P,Q,R,S$ respectively. Note that $B = B_P \cup B_Q \cup B_R \cup B_S$.The inclusion-exclusion principle tells us that : $$ |B| = |B_P| + |B_Q| + |B_R| + |B_S| \\ - |B_P \cap B_Q| - |B_P \cap B_R| - |B_R \cap B_S| - |B_Q \cap B_R| - |B_Q \cap B_S| - |B_R \cap B_S| \\ + |B_P \cap B_Q \cap B_R| + |B_P \cap B_Q \cap B_S| + |B_P\cap B_R\cap B_S| + |B_Q \cap B_R \cap B_S| \\ - |B_P \cap B_Q \cap B_R \cap B_S| $$

therefore, we must calculate each of these. They feel like a lot of terms, but in truth there are not too many of them. Why? Because a lot of them are zero.

---

Let us see this. take $Q$ and $R$. Any path passing through both $Q$ and $R$ must either hit $Q$ or $R$ first. If it hits $Q$ first, then it has to go left to hit $R$, impossible. Similarly, any path hitting $R$ first go down to hit $Q$ , impossible.

Thus, no path can cross both $Q$ and $R$. In short, $|B_Q \cap B_R| = 0$. Similarly, any intersection containing both these terms is $0$.

That now gives us : $$ |B| = |B_P| + |B_Q| + |B_R| + |B_S| \\ - |B_P \cap B_Q| - |B_P \cap B_R| - |B_R \cap B_S| - |B_Q \cap B_S| - |B_R \cap B_S| \\ + |B_P \cap B_Q \cap B_S| + |B_P\cap B_R\cap B_S| $$

However, something similar holds with $P$ and $Q$ (I leave you to see this, in the same manner as above). Then, $|B_P \cap B_Q| = 0$, and terms containing it.

We get to:

$$ |B| = |B_P| + |B_Q| + |B_R| + |B_S| \\ - |B_P \cap B_R| - |B_R \cap B_S| - |B_Q \cap B_S| - |B_R \cap B_S| \\ + |B_P\cap B_R\cap B_S| $$

Each of $|B_P|,|B_Q|,|B_R|,|B_S|$ is calculable in the manner you mention.

However, what we realize, is that the intersection probabilities can also be computed in the iterative fashion in which we computed these ones above.

---

For example, take $|B_P \cap B_R|$. This is counting all paths that go through $P$ and $R$. We see that $P$ must come before $R$. Now, the task is simple, and breaks into three independent tasks.

• Find the up-right paths from $0$ to $P$.

• Find the up-right paths from $P$ to $Q$.

• Find the up-right paths from $Q$ to $(10,10)$.

The first and third of these is easy. For the second, imagine such a path from $P = (3,3)$ to $Q= (3,7)$. Translate such a path down by $3$, and left by $3$ : it becomes an up-right path from $(0,0)$ to $(0,4)$, whence the formula applies. So, by a shift, you can count these , and multiplying the three quantities above, you are done.

Something similar happens for all the other intersections.

---

For $|B_P \cap B_R \cap B_S|$, any path going through each of these first goes to $P$, then $R$ , then $S$. Break up(into four parts), and multiply!

Finally, you can put everything together to finish.