Guichard-Combinatorics-Graph-Theory · Problem 1.3.1

The first part is about counting arrangements: to reach $(i,j)$ in $i+j$ steps, you need to choose which $i$ of those steps go east (the rest go north). This is a binomial coefficient. For the second part, use complementary counting—find all shortest routes that would use the blocked street, then subtract from the total. A route uses that blocked street only if it passes through both $(k,l)$ and $(k+1,l)$, so count paths that go $(0,0) \to (k,l) \to (k+1,l) \to (i,j)$ and subtract.

The first part is about counting arrangements: to reach $(i,j)$ in $i+j$ steps, you need to choose which $i$ of those steps go east (the rest go north). This is a binomial coefficient. For the second part, use complementary counting—find all shortest routes that would use the blocked street, then subtract from the total. A route uses that blocked street only if it passes through both $(k,l)$ and $(k+1,l)$, so count paths that go $(0,0) \to (k,l) \to (k+1,l) \to (i,j)$ and subtract.