Combinatorics - Number of Paths in a Grid with a Hole

Question

Given a $12\times12$ grid with a hole of $4\times4$ in its middle, how many short paths (right or up only) are there from $(0,0)$ to $(12,12)$.

I tried using inclusion-exclusion by counting the number of paths that go through at least one point inside the hole, then count the paths that go through at least 2 points in the hole etc. but so far I got lost. Would appreciate any (perhaps simpler) suggestions to try solve this.

Thanks

Answer 1

Possible hint: the path must go through exactly one of the points on the diagonal line joining the top left to the lower right corner of the grid. Count those for the points not in the hole.

Answer 2

We need a way of grouping the paths into disjoint sets. Let $N_i$ be the number through the point $(i,12-i)$ for $i=0,1,2,3,4,8,9,10,11,12$.

We have $N_i={12\choose i}^2$, so the total number of paths is $2\left({12\choose0}^2+{12\choose1}^2+{12\choose2}^2+{12\choose3}^2+{12\choose4}^2\right)=595852$.