12
$\begingroup$

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.

enter image description here

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?

$\endgroup$
1

2 Answers 2

23
$\begingroup$

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

$\endgroup$
9
  • $\begingroup$ I was over thinking it.... Thanks $\endgroup$
    – Rustyn
    Mar 5, 2013 at 7:34
  • $\begingroup$ @Rustyn: You’re welcome. $\endgroup$ Mar 5, 2013 at 7:35
  • $\begingroup$ 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. $\endgroup$
    – Rustyn
    Mar 5, 2013 at 7:44
  • $\begingroup$ so 2* C_20 = 13128240840 + cases where the route passes the main diagonal. $\endgroup$
    – Rustyn
    Mar 5, 2013 at 7:55
  • 1
    $\begingroup$ @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$. $\endgroup$
    – dtldarek
    Mar 5, 2013 at 7:58
3
$\begingroup$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.