Lattice paths and Catalan Numbers

Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.

How many such routes are there through a 20×20 grid?

This is a problem I was working on a while ago from http://www.projecteuler.net

It occurred to me that I could count the number of routes using Catalan numbers, so I started to go that route but couldn't come up with the right answer. I got really complicated expressions, and ultimately ended up missing possible routes and/or overcounting.

How do I use Catalan Numbers to count the number of routes?

You don’t need Catalan numbers: you just need binomial coefficients. The number of such paths in an $m\times n$ grid is $\binom{m+n}m=\binom{m+n}n$.

The reason is quite simple: you must make a total of $m+n$ moves, consisting of $m$ moves down and $n$ to the right, in any order, and there are $\binom{m+n}m$ ways to choose which of the $m+n$ moves are down (or, equivalently, $\binom{m+n}n$ ways to choose which $n$ of them are to the right).

In addition to the above solution this can done in the following way:

    class Program
{
    static void Main(string[] args)
    {

        Console.WriteLine( Program.LatticePaths(20, 20));

    }//end of main

    public static Int64 LatticePaths(int rows, int columns)
    {
        Int64[,] paths = new Int64[rows + 1, columns + 1];

        for (int row = 0; row <= rows; row++)
        {
            for (int column = 0; column <= columns; column++)
            {
                if (row == 0 || column == 0)
                    paths[row, column] = 1;
                else
                    paths[row, column] = paths[row - 1, column] + paths[row, column - 1];
            }
        }

        return paths[rows, columns];
    }

}

Also, Pascal's triangle can solve this problem as well:

       1 1
1X1    1 2 1
       1 3 3  1
2X2    1 4 6  4  1
       1 5 10 10 5  1
3X3    1 6 15 20 15 6

Note that the solutions for a 1x1 grid is 2, a 2x2 grid is 6, and a 3x3 grid is 20. So, the highest number for 40X40 is the answer for this problem! C# program can be written in following way:

    class Program
{
    static void Main(string[] args)
    {
        long row = 40, col = 40;
        long[,] p = new long[row, col];
        p[0, 0] = 1;
        p[0, 1] = 1;

        for (int i = 1; i < row; i++)
        {
            for (int j = 0; j <= i+1; j++)
            {
                if (j > row-1) break;
                if (j == 0)
                {
                    p[i, j] = 1;

                }
                else 
                    p[i, j] = p[i - 1, j] + p[i - 1, j - 1];
            }

        }

        for (int i = 0; i < row; i++)
        {
            for (int j = 0; j < col; j++)
            {
                if(p[i, j]>0)Console.WriteLine(p[i, j]);
            }
            Console.WriteLine("");
        }
    }
}