Caminos de longitud n en $\mathbb{Z}^2$ dado el punto inicial y punto final fijo

Question

Considere la posibilidad de $\mathbb{Z}^2$ como un infinito cuadrícula donde los nodos son los elementos , elegir un punto de partida $x$ y un extremo de $y$.
Deje $n$ ser un número natural, nos gustaría saber el número de caminos de $x$ $y$con exactamente la longitud de la $n$.
Por un camino de $p : \{1,...,n\} \to \mathbb{Z}^2$ a ser una solución válida ha de satisfacer las siguientes condiciones:

1. $p(1) = x$ $p(n) = y$.
2. El camino es inyectiva, lo que significa $p(i) \neq p(j)$ si $i \neq j$.
3. $p(i+1) = p(i) \pm (1,0)$ o $p(i+1) = p(i) \pm (0,1)$.

Si descartamos la segunda condición, el problema fue resuelto más de aquí.
Yo no entiendo por qué el dado recusive forma es una solución al problema planteado.
Tal vez a entender el porqué de que la solución es correcta sería útil para este problema.

ejemplo

Sin pérdida de generalidad podemos asumir $x = (0,0)$ deje $y = (1,1)$ claramente que no habrá caminos de desigual longitud.
La secuencia de los 10 primeros números impares es: $(2 , 4, 16, 76, 396, 2164, 12240, 71024, 20436, 2528780)$.
Graficar en un semilogarithmic escala: .
Podemos ver una exponencial-como gráfico.
(por supuesto, esto es sólo un ejemplo para $y = (1,1)$ sería bueno tener una forma cerrada para todos los $y$)

He probado algunos otros ejemplos también todos parecen mostrar exponencial como el comportamiento cuando no son cero, no puedo calcular una gran cantidad de términos, pero parece que crece un poco más rápido que la exponencial: $t_n/t_{n-1}$ parece crecer.
Para el ejemplo de (0,0) a (1,1) los términos de la secuencia de las fracciones de aproximadamente $(2, 4, 4.75, 5.21, 5.46, 5.66, 5.80, 5.92, 6.01) $
Gráfico:

Parece que las fracciones posiblemente convergen.

basecase

Si hemos de esperar a probar explícita o de forma recursiva la prueba será probablemente con la inducción en $n$.
Aquí puedo demostrar la basecase: el número de caminos distintos con un mínimo de distancia, la prueba estará en el más general de la configuración de $\mathbb{Z}^p$.

Vamos $x=(0,0, ... ,0)$, $y = (y_1, y_2, ... , y_p)$.

Por un camino de $p:\{1,2, ...,d\} \to \mathbb{Z}^p $ $x$ $y$a ser de longitud mínima es necesario y suficiente que $p$ es monotono en cada componente.
Desde $p$ tiene que terminar en $y$: $\sum_i(\delta_i) = \sum_i(p(i+1) - p(i)) = y$.
Aquí $\delta_i \in \{\mbox{sign(}y_j)\cdot e_j | j \in \{1,2,...,p\}\}$
$e_j$ es la j-esima base de vectores para $\mathbb{Z}^p$ en el estándar de la base.
Cada permutación de las $\delta_i$'s se traducirá en un camino de longitud mínima de$x$$y$. Para ello el número de caminos de longitud mínima es igual a $$\frac{(d-1)!}{\lvert y_1\rvert!\cdot \lvert y_2 \rvert!\cdot ...\cdot \lvert y_p \rvert!}$$ $$\tag*{$\blacksquare$}$$

Answer 1

Hay buenas noticias y malas noticias. La buena noticia es que no es una buena fórmula para el número de rutas en $\mathbb{Z}^2$ a partir de un punto a otro como una suma de coeficientes multinomiales, frente a la fórmula recursiva que estás vinculado. También, es sencillo generalizar esta fórmula a las dimensiones superiores. La mala noticia es que la enumeración de las inyectiva rutas probablemente requiere de la inclusión-exclusión principio, por lo que la fórmula resultante no será tan agradable.

General de caminos, vamos a $x$ $y$ puntos en $\mathbb{Z}^2$, vamos a la (firmado) horizontal y vertical de los desplazamientos entre el $x$ $y$ $h$ $v$ ( $\mathbb{Z}$ ), y deje $P_{x,y,n}$ el número de caminos de longitud $n$ entre los puntos de $x$$y$. Una ruta de acceso es equivalente a una secuencia de movimientos a la izquierda, derecha, arriba o abajo. Deje $l, r, u, d \ge0$ el número de tales movimientos, respectivamente. Entonces, teniendo en cuenta el número total de movimientos, $$l+r+u+d=n$$ y teniendo en cuenta la horizontal y vertical de los desplazamientos $$r-l=h,\quad u-d=v.$$ If $l,r,u,d$ satisfy these conditions, there are exactly the multinomial coefficient $\binom{n}{l,r,u,d} $ paths from $x$ to $s$ in $$ n pasos. Así, $$P_{x,y,n}=\sum_{l,r,u,d}\binom{n}{l,r,u,d},$$ donde los índices de la suma son enteros no negativos satisfacer las tres condiciones. Se puede resolver el sistema de tres ecuaciones con cuatro variables para reescribir la suma con un solo índice, por ejemplo $$P_{x,y,n}=\sum_{l\ge0}\binom{n}{l,l+h,\frac{n-h-v}2-l,\frac{n-h+v}2-l}.$$

Ahora, para el caso de la inyectiva caminos, podemos usar la inclusión-exclusión principio. De la colección general de caminos, restar aquellos que tienen al menos un punto de intersección (en el tiempo y en el espacio), dejando $P_{x,y}-\sum_{m,z}P_{x,z,m}P_{z,y,n-m}.$ sin Embargo, esta resta caminos con al menos dos puntos de intersección de dos veces, así que tenemos que añadir estas de vuelta, dejando a las $$P_{x,y}-\sum_{m,z}P_{x,z,m}P_{z,s,n-m}+ \sum_{m_1,m_2,z_1,z_2}P_{x,z_1,m_1}P_{z_1,z_2,m_2}P_{z_2,y,n-m_1-m_2}-\cdots,$$ etc. Si hay una manera más directa la enumeración de los inyectiva caminos evitando el uso de la inclusión-exclusión principio, me sorprendería (pero agradable).