How many routes from $(0,0)$ to $(2n,2n)$ avoiding $(2k+1,2k+1)$?

118 Views Asked by At

Imagine a two-dimensional grid that all $(2k+1, 2k+1)$ are prohibited. Suppose the origin $(0,0)$ is in the bottom-left corner and the point $(2n,2n)$ is the top-right corner. A path on the grid consists of a series of moves in which each move is either one unit to the right or one unit up. Diagonal moves are not allowed. How many different ways are there to construct a path starting at $(0,0)$ and ending at $(2n,2n)$, avoiding all the prohibited points $(2k+1, 2k+1)$?

I'm a little stuck on this one. Seems it can be counted by a lot of inclusive-exclusive computation, but is there a simpler result?