No sé de una combinatoria de la solución, pero sí sé que un truco...
El número de $n$-paso paseos de partida en $(x,y)$ que no salga de la cuadrícula es, obviamente, el número total de $n$-paso caminatas ($4^n$) veces la probabilidad de $p_n(x,y)$ que un random $n$-paso pie comenzó a $(x,y)$ no salir de la red.
¿Qué es que la probabilidad? Obviamente, $p_0(x,y) = \chi(x,y)$ donde $\chi(x,y)$ es igual a $1$ dentro de la red y $0$ sobre los puntos que lo rodean. Para mayor $n$, tenemos la relación de recurrencia $$p_{n+1}(x,y) = \chi(x,y) \frac{p_n(x-1,y) + p_n(x+1,y) + p_n(x,y-1) + p_n(x,y+1)}{4}.$$
Excepto para el $\chi(x,y)$ plazo, esto es casi una convolución, y haciendo uso del hecho de que la red es rectangular, podemos deshacernos de los no deseados plazo mediante la ampliación de $p_0$ adecuadamente más allá de los bordes de la cuadrícula.
Aquí resulta ser mucho más conveniente dejar que la cuadrícula se extienden desde $(1,1)$$(a-1, b-1)$, así que me voy a la adopción de este convenio y, a continuación, defina $p_0(x,y) = f(x)g(y)$ donde $$f(x) = \begin{cases} \phantom{+}0 & \text{if }x = ka, k \in \mathbb Z \\ \phantom{+}1 & \text{if }(2k+0)a < x < (2k+1)a, k \in \mathbb Z \\ -1 & \text{if }(2k+1)a < x < (2k+2)a, k \in \mathbb Z \end{cases}$$
$$g(y) = \begin{cases} \phantom{+}0 & \text{if }y = kb, k \in \mathbb Z \\ \phantom{+}1 & \text{if }(2k+0)b < y < (2k+1)b, k \in \mathbb Z \\ -1 & \text{if }(2k+1)b < y < (2k+2)b, k \in \mathbb Z.\end{cases}$$
Por tanto, no es difícil mostrar que, incluso si dejamos caer el $\chi(x,y)$ plazo de la recurrencia, $p_n(x,y) = 0$ siempre $x$ es divisible por $a$ o $y$ es divisible por $b$. Por lo tanto, podemos calcular el $p_{n+1}$ $n \ge 0$ a través de la convolución $p_{n+1} = p_n * K$, es decir,$$p_{n+1}(x,y) = \sum_{u,v \in \mathbb Z} p_n(x-u,y-v) K(u,v),$$ where the kernel $ K$ is given by $K(1,0) = K(0,1) = K(-1,0) = K(0,-1) = \frac 1 4$ and $K(u,v) = 0$ for all other values of $u$ and $v$.
¿Por qué queremos hacerlo? Bien, lo que ocurre es que las circunvoluciones de discretos funciones periódicas pueden ser eficientemente calculado utilizando discreta de Fourier. En particular, dejando $\tilde p_n$ $\tilde K$ denotar las transformadas de Fourier de $p_n$$K$,$$\tilde p_n = \tilde p_{n-1} \tilde K = \tilde p_0 \tilde K^n,$$, donde la multiplicación se hace simplemente pointwise.
