¿Cuántas formas hay para atravesar una cuadrícula de 3 por 3 de manera que comience en (0,0) y termine en (2,2)?

Question

De cuántas maneras existen para atravesar un $n$ $n$ red que empiece en $(0,0)$ y final en $(n-1,n-1)$ si se dan estas condiciones:

1)puede atravesar cada rama en la que más de una vez.

2)Usted puede pasar a través de cada nodo en la mayoría de una sola vez.

3)Usted puede ir al norte, sur, este y oeste.

Estoy familiarizado con una pregunta similar, donde solo se puede ir al norte y oriente, pero la pregunta es significativamente más difícil cuando se trata de agregar estas otras direcciones. Inicialmente probé haciendo esto el uso de la combinatoria y luego, por inducción, tanto en vano. Luego se centró en el 3 por 3 cuadrícula ($n=1,2$ son simples) y comenzó a romper el 3 por 3 cuadrícula en pequeñas y pequeñas redes y contó con las formas de llegar desde el nuevo punto de las pequeñas redes a $(2,2)$ y el agregado. Tengo 2 caminos para un 1 por 1 cuadrícula, 12 maneras para que un 2 por 2 de cuadrícula, y 152 rutas de acceso para un 3 por 3 cuadrícula (no del todo seguro de si esto es correcto, pero creo que el proceso es válido).

Yo era incapaz de generalizar (o validar mi solución para $n=1,2,3$) este problema para una $n$ $n$ cuadrícula. Cómo hacer esto?

Answer 1

Su número de rutas de acceso para un 2×2 de la cuadrícula es la correcta, pero que para un 3×3 de la cuadrícula está mal: hay 184 caminos, no 152.

Esta secuencia, el número de auto-evitar los paseos entre las esquinas opuestas de un $n×n$ red, es OEIS A007764. Aunque no hay una fórmula fácil, uno de los enlaces que hay detalles Knuth del método para calcular estos números para cualquier gráfica y su especialización a la cuadrícula de gráficos, que me animo a leer.