Encontrar el Número total de Ruta de longitud L

Question

encontrar el número de la ruta entre dos puntos en una cuadrícula en la que sólo puede mover una unidad hacia arriba, abajo, izquierda o derecha? Existe una formula para esto?.

Cualquier camino más corto de $(0,0)$ $(m,n)$incluye a $m$ pasos en el eje x y $n$ pasos en el eje y. Esto es contado por el coeficiente binomial $\binom{m+n}{m} = \binom{m+n}{n}$.

Pero, ¿qué número sobre el total de la ruta de Longitud L en una cuadrícula y de volver a la celda ?

Answer 1

El método clásico para contar el número de caminos de longitud $L$ en un gráfico de $G$ son para tomar la correspondiente matriz de adyacencia $A$ y calcular el $A^L$.

Ni idea de si este enfoque puede ser utilizado para dar una forma cerrada etc solución, aunque.

Answer 2

Deje $[x^p]$ el valor del coeficiente de $x^p$ en una serie de $A(x)$.

Consideramos entramado de caminos en $\mathbb{Z}\times\mathbb{Z}$ de la longitud de la $L$ $(0,0)$ $(m,n)$con los pasos en la dirección $(1,0),(0,1),(-1,0)$$(0,-1)$. El número de rutas es dada como: \begin{align*} \color{blue}{[x^my^nt^L]}&\color{blue}{\frac{1}{1-t\left(x+y+\frac{1}{x}+\frac{1}{y}\right)}}\\ &=[x^my^n]\left(x+y+\frac{1}{x}+\frac{1}{y}\right)^L\tag{1}\\ &=[x^my^n]\sum_{j=0}^L\binom{L}{j}\left(x+\frac{1}{x}\right)^j\left(y+\frac{1}{y}\right)^{L-j}\tag{2}\\ &=\sum_{j=0}^L\binom{L}{j}[x^{m}]x^{-j}(1+x^2)^j[y^{n}]y^{-L+j}(1+y^2)^{L-j}\tag{3}\\ &=\sum_{j=0}^L\binom{L}{j}[x^{m+j}](1+x^2)^j[y^{n+L-j}](1+y^2)^{L-j}\tag{4}\\ &\color{blue}{=\sum_{{j=0}\atop{{\,\,m\,\equiv\,j(2)}\atop{n+L\,\equiv\,j(2)}}}^L\binom{L}{j}\binom{j}{\frac{m+j}{2}}\binom{L-j}{\frac{n+L-j}{2}}}\tag{5} \end{align*}

Comentario:

• En (1) expandir la serie geométrica y seleccionar el coeficiente de $t^L$.

• En (2) aplicamos el teorema del binomio.

• En (3) se utiliza la linealidad del coeficiente de operador y hacer algunos reordenamientos como preparación para el siguiente paso.

• En (4) aplicamos la regla de $[z^{p+q}]A(z)=[z^p]z^{-q}A(z)$.

• En (5) seleccionamos los coeficientes de $x^{m+j}$$y^{n+L-j}$.

Caso especial $L=m+n$

Ponemos a $L=m+n$ y obtener a partir de (5)

\begin{align*} \sum_{{j=0}\atop{\,\,m\,\equiv\,j(2)}}^{m+n}&\binom{m+n}{j}\binom{j}{\frac{m+j}{2}}\binom{m+n-j}{n+\frac{m-j}{2}}\tag{6}\\ &=\sum_{j\color{blue}{=m}}^{\color{blue}{m}}\binom{m+n}{j}\binom{j}{\frac{m+j}{2}}\binom{m+n-j}{n+\frac{m-j}{2}}\tag{7}\\ &\color{blue}{=\binom{m+n}{m}} \end{align*} como era de esperar.

Comentario:

• En (6) se puede omitir una restricción desde $n+L\equiv n+(n+m)\equiv m(2)$.

• En (7) se observa que la media de coeficiente binomial $\binom{j}{\frac{m+j}{2}}=0$ si $j<m$. Tomamos nota también de la mano derecha coeficiente binomial $\binom{m+n-j}{n+\frac{m-j}{2}}=0$ si $j>m$. Por lo tanto, podemos restringir el rango del índice de $j$$\{m\}$.

Answer 3

Número Total de paseos a partir de la longitud L de un Punto a a A a A está dado por

número de paseos posibles es $$\sum_{k=0}^{L/2}\frac{L!}{k!^2(L/2-k!)!^2}={L\choose L/2}\sum_{k=0}^{L/2}{L/2\choose k}^2={L\choose L/2}^2$$

Since you are calculating from point A to B , so shortest path will be of distance $:X =|A. x B. X| , Y=|A. y B. s| , S=X+Y$ , now just iterate towards the remaining length

$$\sum_{k=0}^{L-S}\frac{L!}{k/2!(L-S-k)/2!*(X+K/2)!*(Y+(L-S-k)/2)!} $$

Note: $K$ is incremented twice i.e $K=K+2$ and some base condition also $(L-S)$ debe ser aún más no habrá camino