# 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?

• Mar 8, 2013 at 9:51

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).

• I was over thinking it.... Thanks Mar 5, 2013 at 7:34
• @Rustyn: You’re welcome. Mar 5, 2013 at 7:35
• Is there still a way to count the # of routes using Catalan numbers? I would be interested to know... Although I do feel it would be a lot more difficult as $C_n$ is the number of monotonic paths along the edges of a grid with n × n square cells, which do not pass above the diagonal. Mar 5, 2013 at 7:44
• so 2* C_20 = 13128240840 + cases where the route passes the main diagonal. Mar 5, 2013 at 7:55
• @RustynYazdanpour $C_n = \frac{1}{n+1}\binom{2n}{n}$, so if you really, really wish, for square grids $n \times n$ you could use $(n+1)C_n$. Mar 5, 2013 at 7:58

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("");
}
}
}