Vamos a generar todo el entramado de caminos con $h$ horizontal se mueve, $v$ vertical se mueve y $c$ cambios en la dirección. El número de celosía caminos será el $x^hy^vz^c$ coeficiente de algunos de generación de la función de la serie de $f(x,y,z)$.
Esta función se puede dividir en función de todos esos caminos que terminan con un mover horizontal $f_x(x,y,z)$, en función de todos esos caminos que terminan con un mover vertical $f_y(x,y,z)$ y la ruta vacía $1$.
$$f=1+f_x+f_y\, .\tag{1}$$
Ahora, los caminos que terminan en un mover horizontal $f_x$ son
- un solo movimiento $x$,
- un camino que termina en un mover horizontal $f_x$, seguido por otro mover horizontal $x$,
- un camino que termina en un verical mover$f_y$, seguido por un mover horizontal $x$ y por lo tanto también un cambio en la dirección $z$.
$$\begin{align} && f_x&=x+f_xx +f_yxz\\[1ex]
&\implies & f_x&=\frac{x+f_yxz}{1-x}\, .\tag{2}\end{align}$$
Del mismo modo podemos argumentar para $f_y$:
$$\begin{align} &&f_y&=y+f_yy+f_xyz\\[1ex]
&\implies & f_y&=\frac{y+f_xyz}{1-y}\, .\tag{3}\end{align}$$
Podemos sustituir el $(3)$ $(2)$ eliminando $f_y$ dar:
$$\begin{align} &&f_x&=\frac{x}{1-x}+\frac{xyz}{(1-x)(1-y)}+\frac{f_xxyz^2}{(1-x)(1-y)}\\[1ex]
&\implies &f_x&=\frac{x(1-y)+xyz}{(1-x)(1-y)-xyz^2}\, .\tag{4}\end{align}$$
Del mismo modo eliminando $f_x$ tenemos
$$f_y=\frac{y(1-x)+xyz}{(1-x)(1-y)-xyz^2}\, ,\tag{5}$$
a continuación, la introducción de $(4)$ $(5)$ a $(1)$ y simplificando, se obtiene:
$$f(x,y,z)=\frac{1-xy(1-z)^2}{1-x-y+xy-xyz^2}\, .\tag{6}$$
Esta es nuestra generación la función para la red de rutas con cambios de dirección.
Podríamos, en este punto, usar un sistema algebraico por computadora un sabio para encontrar los coeficientes de todas las $x^8y^6z^{\text{even}}$$(6)$, a continuación, agregarlos a recibir nuestra respuesta. Sin embargo, hay un truco útil que podemos usar, llamada la transformada de Fourier Discreta (DFT) que hará que nuestra respuesta fácil de calcular.
Tomamos nota de que la solución deseada sería el $x^8y^6$ coeficiente de
$$\begin{align}\tfrac{1}{2}(f(x,y,1)+f(x,y,-1))&=\frac{1-2xy}{1-(x+y)}\\[1ex] &=\sum_{k\ge 0}(x+y)^k-2xy\sum_{k\ge 0}(x+y)^k\end{align}\tag{7}$$
ya que estamos utilizando la raíz cuadrada de la unidad $\{1,-1\}$ impar poderes de $z$ cancelar y le suma la aún coeficientes.
Así, la necesaria $x^8y^6$ coeficiente con el operador $[x^8y^6]$$(7)$:
$$\begin{align}[x^8y^6]\tfrac{1}{2}(f(x,y,1)+f(x,y,-1))&=[x^8y^6]\sum_{k\ge 0}(x+y)^k-2[x^7y^5]\sum_{k\ge 0}(x+y)^k\\[1ex] &=\binom{8+6}{6}-2\binom{7+5}{5}\\[1ex] &=\binom{14}{6}-2\binom{12}{5}\\[1ex]& =1419\tag{Answer}\end{align}$$
