Number of paths in a MxN matrix Given a MxN grid, how many paths can there be to reach the bottom right cell from the top left cell?
The only constraints are one cannot visit a cell more than once, I tried checking the other solutions but they only consider right and down moves whereas this one can have left and up moves too. Any help is appreciated :)
For example, consider a 3x3 matrix,
I converted into a graph as shown below:

where the numbers associated with node represent cell number counting from top left to bottom right, then the number of paths would be 12 as shown below:
    {
    {1, 2, 3, 6, 5, 4, 7, 8, 9}, {1, 2, 3, 6, 5, 8, 9}, {1, 2, 3, 6, 9}, 
    {1, 2, 5, 4, 7, 8, 9}, {1, 2, 5, 6, 9}, {1, 2, 5, 8, 9},
    {1, 4, 5, 2, 3, 6, 9}, {1, 4, 5, 6, 9}, {1, 4, 5, 8, 9},
    {1, 4, 7, 8, 5, 2, 3,6, 9}, {1, 4, 7, 8, 5, 6, 9}, {1, 4, 7, 8, 9}
    }
The above paths are shown below:

Even though I show each and every path here, I don't need them , I just need the count stating number of paths possible
 A: If m==n you can find the no of paths to reach the bottom right cell from the top left cell using slight modification of Backtracking problem. Find below the code in 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;
    }

}

A: For the case $M=N$ this is OEIS A$007764$; no closed form, recurrence, or generating function is given. There is a link to this paper, which has information on asymptotics for this and related problems; I have not looked at it in any detail, however. Finally, there is an OEIS Wiki stub that gives the figures for $N\le M\le 6$ and shows question marks for other values unless $M=N$ or $N\le 2$.
A: As @Shailesh mentioned in the comments, you can do this with a recurrence relation. Suppose you have reached the bottom left corner by some series of steps. Now, go back one step: you are now either at the node above the corner, or beside it. If we write the number of ways to reach the corner node of an $m \times n$ grid as $a_{m,n}$, then we can write
$$a_{m,n} = a_{m,n-1} + a_{m-1,n}$$
because you must first reach the penultimate node, and then take the final step. Note that $a_{m,n} = a_{n,m}$ because we are essentially counting the same thing. The initial values for this recurrence are $a_{1,1} = 1$, $a_{m,0} = a_{0,m} = 0$.
An interesting fact, however, arises now. If you write the values of $a_{m,n}$ in a grid, you will see that every number is the sum of the number above it and the number beside it... and the first row and column are both filled with 1s! This is nothing but (try to find this yourself first)

 Pascal's triangle, and the numbers are binomial coefficients.

