Número de paseos en 2D de la cuadrícula

Question

Supongamos que estamos en un finitos 2D cuadrícula de puntos de$(0,0)$$(a,b)$. Cada vuelta que se puede mover arriba/abajo/izquierda/derecha en esta cuadrícula (tenemos 3 posibles movimientos en los bordes y 2 en las esquinas). En el principio estamos en el punto de $(x_0,y_0)$ dentro de la red. De cuántas maneras existen para hacer de $N$ pasos en la cuadrícula?

Sé que una solución recursiva cuando el número de maneras de hacer $N$ pasos es la suma del número de maneras de hacer $N-1$ pasos de la celda a la izquierda/derecha/arriba/abajo. Me pregunto ¿hay una combinatoria solución?

Answer 1

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.

Answer 2

Muy elegante la respuesta de Ilmari. Sin embargo, parece que por este procedimiento tambien recuento de los "degenerados" caminos " en el siguiente sentido: supongamos, por ejemplo, que estamos en el paso 1 y en el punto de $(x_{1},y_{1})$ tal que $x_{1} = x_{0}$$y_{1} = y_{0}+1$. Ahora, para el próximo paso que no puede moverse hacia atrás hasta el punto anterior $(x_{0},y_{0})$, de lo contrario $(x_{2},y_{2}) = (x_{0},y_{0})$ y el trazado de la ruta sólo tendría dos puntos de $\left \{ (x_{0},y_{0}), (x_{1},y_{1}) \right \}$. De la misma manera, si en cada paso todavía tenemos 4 posibles movimientos, que sería el recuento de estos "degenerados" caminos", es decir, de los caminos por los que después de haber hecho cualquier número de movimientos, el seguimiento es el mismo.