Hay un problema bastante común para encontrar rutas que generalmente se indica de la siguiente manera:
Considere una cuadrícula de 4 filas por 4 columnas con la esquina superior izquierda denominada A y la esquina inferior derecha denominada B.
Suponga que comenzando en el punto A puede ir un paso hacia abajo o un paso hacia la derecha en cada movimiento. Esto se continúa hasta llegar al punto B. ¿Cuántos caminos diferentes de A a B son posibles?
Este problema es muy fácil de resolver. Una solución .
Sin embargo, este problema se vuelve extraordinariamente más difícil si ignoramos la restricción de dirección:
puede ir un paso hacia abajo o un paso hacia la derecha en cada movimiento.
La única regla es que no puedes pasar por la misma celda dos veces.
¿Es posible determinar el número de rutas únicas de A a B sin simplemente probar todas las rutas posibles?
¿ Podemos aplicar nuestra solución a cualquier n x ngrilla? ¿ Qué pasa con cualquier m x nrejilla?
(PD: esta no es una pregunta de tarea. Se me ocurrió hace unas horas y he estado tratando de resolverla desde entonces).
Creo que este es el problema de contar los paseos de torre que se evitan a sí mismos , y para el caso cuadrado, puede buscar aquí los primeros valores en el OEIS aquí . Desafortunadamente, parece que no existe una expresión de forma cerrada conocida para . Hay más información y referencias en Mathworld .
Dan
Dan