How many routes are there that pass through at most one congested intersection

Question

I am trying to solve the following problem, but i am not quite sure how to attack.

Problem Description

A taxi drives from the intersection labeled A to the intersection labeled B in the grid of streets shown below. The driver only drives north (up) or east (right). Traffic reports indicate that there is heavy congestion at the intersections identified. How many routes from A to B can the driver take that pass through at most one congested intersection? Some Problem analysis Obviously there are $ \binom {16} {10}$ routes from A to B and moving upwards in the picture, $ \binom {5} {4}$, $ \binom {9} {7}$, $ \binom {5} {2}$ and $ \binom {13} {8}$ routes to each congestion point from A, but i am not quite sure how to extend this further. I thought about counting the complement case but that does not seem any simpler to me either. Any help or suggestions would be much appreciated.

Answer 1

This is a typical candidate for inclusion-exclusion. Number the congested intersections from left to right by the index set $[4]=\{1,2,3,4\}$, and let $P_i$ be the set of paths that go through intersection $i$. Also abbreviate $P_I=\bigcap_{i\in I}P_i$ for any subset $I\subseteq[4]$, in particular $P_\emptyset$ is the set of all paths. The number $p_I=|P_I|$ can easily be computed for each $I$ (and in many cases it is $0$).

You need to compute the size of the complement of $\bigcup_{I\in\binom{[4]}2}P_I$. This size is given by $$\begin{align} &p_\emptyset-p_{14}-p_{23}-p_{24}-p_{34}+2p_{234} \\&=\tbinom{16}6 -\tbinom53\tbinom82\tbinom31 -\tbinom51\tbinom41\tbinom74 -\tbinom51\tbinom84\tbinom31 -\tbinom92\tbinom43\tbinom31 +2\tbinom51\tbinom41\tbinom43\tbinom31\\ &=8008-10*28*3-5*4*35-5*70*3-36*4*3+2*5*4*4*3\\&=5466 \end{align} $$ This formula is most easily justified by checking that every path contributes $1$ to this sum if it passes through at most $1$ congested point, and $0$ otherwise; for instance a path passing through the congested points $2,3,4$ is first added in $p_\emptyset$, then subtracted thrice in the terms $-p_{23}-p_{24}-p_{34}$ and finally added back twice in the term $+2p_{234}$, for a net contribution of $0$.

Answer 2

Label the congested intersections from left to right $W,$ $X,$ $Y,$ $Z.$

Using complement will be helpful: subtract from the total number of paths from $A$ to $B$ the number of paths that pass through two or more of the labeled intersections. For a path to pass through $W$ and $Z,$ for example, it has to pass from $(0,0)$ to $(2,3),$ and then from $(2,3)$ to $(8,5),$ and then from $(8,5)$ to $(10,6).$ You can work out how many ways there are to do each leg of this route, and then the number of ways of doing all three legs.

If you subtract the number of paths that go through both $X$ and $Y,$ the number of paths that go through both $X$ and $Z,$ and the number of paths that go through both $Y$ and $Z,$ you'll realize that some paths have been subtracted multiple times. These will have to be added back in.