Número de caminos en una matriz MxN

Si m == n, puede encontrar el número de rutas para llegar a la celda inferior derecha desde la celda superior izquierda usando una ligera modificación del problema de retroceso. Encuentra debajo el código en Java.

public class Robot {
    private static int count = 0;
    public static void main(String[] args) {
        Robot robot = new Robot();
        int m = 5, n = 5;
        boolean Visited[][] = new boolean[5][5];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++)
                Visited[i][j] = false;
        }
        robot.traverse(Visited, 0, 0, m, n);
        System.out.println(count);
    }
    /**
     * 
     * @param Visited array
     * @param index i
     * @param index j
     * @param max Row m
     * @param max column n
     */
    private void traverse(boolean Visited[][], int i, int j, int m, int n){
        if(i==m-1&&j==n-1){
            count++;
            return;
        }
        if(isSafe(i, j, m, n, Visited)){
            Visited[i][j]=true;
            traverse(Visited, i, j+1, m, n);
            traverse(Visited, i+1, j, m, n);
            traverse(Visited, i-1, j, m, n);
            traverse(Visited, i, j-1, m, n);
            Visited[i][j] = false;
        }
    }
    /**
     * 
     * @param index i
     * @param index j
     * @param max Row m
     * @param max Column n
     * @param Visited array
     * @return isSafe or not
     */
    private boolean isSafe(int i, int j, int m, int n, boolean Visited[][]){
        if(i>=0&&j>=0&&i<m&&j<n&&!Visited[i][j])
            return true;
        else
            return false;
    }

}

Para el caso$M=N$esto es OEIS A$007764$; no se da ninguna forma cerrada, recurrencia o función generadora. Hay un enlace a este documento , que tiene información sobre asintóticos para este y otros problemas relacionados; Sin embargo, no lo he mirado en detalle. Finalmente, hay un stub de OEIS Wiki que da las cifras de$N\le M\le 6$y muestra signos de interrogación para otros valores a menos que$M=N$o$N\le 2$.

Como @Shailesh mencionó en los comentarios, puede hacer esto con una relación de recurrencia . Suponga que ha llegado a la esquina inferior izquierda por una serie de pasos. Ahora, retroceda un paso: ahora está en el nodo sobre la esquina o al lado. Si escribimos el número de formas de llegar al nodo de la esquina de un$m \times n$rejilla como$a_{m,n}$, entonces podemos escribir

Sin embargo, ahora surge un hecho interesante. Si escribes los valores de$a_{m,n}$en una cuadrícula, verá que cada número es la suma del número de arriba y el número de al lado... ¡y la primera fila y la primera columna están llenas de 1! Esto no es más que (trata de encontrarlo tú mismo primero)

Triángulo de Pascal , y los números son coeficientes binomiales .