Counting in a rectangular grid with obstacles

Solution 1:

Update: This answer is unnecessarily complicated for this case, as you can see from Gerry Myerson’s comment and the simpler calculation in the comment underneath. I’m leaving this here nevertheless since it shows how to do the calculation in the general case when this simplification is not available.

You can do this using inclusion–exclusion. There are $\binom{m+n}m$ ways to go from $(0,0)$ to $(m,n)$ with upward and rightward steps. You have four conditions corresponding to the four points not to be used. The number of ways to use some subset of the excluded points is the number of ways to go from $(0,0)$ to the bottom left point of the subset, then from that to the top right point of the subset, and then from that to $(8,8)$. Thus by inclusion–exclusion the number of admissible paths is

$$ \binom{8+8}8-\binom{3+3}3\binom{5+5}5-\binom{3+4}3\binom{5+4}5-\binom{4+3}4\binom{4+5}4-\binom{4+4}4\binom{4+4}4+\binom{3+3}3\binom{4+5}4+\binom{3+3}3\binom{5+4}5+2\binom{3+3}3\binom{4+4}4+\binom{3+4}3\binom{4+4}4+\binom{4+3}3\binom{4+4}4-\binom{3+3}3\binom{4+4}4-\binom{3+3}3\binom{4+4}4=12870 – 20\cdot252-35\cdot126-35\cdot126-70\cdot70+20\cdot126+20\cdot126+2\cdot20\cdot70+35\cdot70+35\cdot70-20\cdot70-20\cdot70=4050\;, $$

where the $2$ counts the two ways to get from $(3,3)$ to $(4,4)$ and the missing terms in the inclusion–exclusion sum are not included (i.e. excluded ;-) because there's no way to use both $(3,4)$ and $(4,3)$.