Caminos de celosía y números catalanes

Question

Comenzando en la esquina superior izquierda de un 2×2 de la cuadrícula, y el único ser capaz de moverse a la derecha y abajo, hay exactamente 6 rutas a la esquina inferior derecha.

Cuántas de estas rutas son a través de un 20×20 cuadrícula?

Este es un problema en el que estaba trabajando hace un tiempo de http://www.projecteuler.net

Se me ocurrió que podía contar el número de rutas utilizando catalán números, así que empecé a ir por ese camino, pero no podía llegar a la respuesta correcta. Me puse muy complicadas expresiones, y finalmente terminó perdiendo posibles rutas y/o overcounting.

¿Cómo puedo utilizar el catalán Números para contar el número de rutas?

Answer 1

No necesitas números catalanes: solo necesitas coeficientes binomiales. El número de estas rutas en una cuadrícula$m\times n$ es$\binom{m+n}m=\binom{m+n}n$.

La razón es bastante simple: debe realizar un total de movimientos$m+n$, que consiste en$m$ se mueve hacia abajo y$n$ a la derecha, en cualquier orden, y hay$\binom{m+n}m$ formas de elegir cuál de los movimientos$m+n$ están abajo (o, equivalentemente,$\binom{m+n}n$ formas de elegir qué$n$ de ellos están a la derecha).

Answer 2

Además de la solución anterior, esto puede hacerse de la siguiente manera:

     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];
    }

}
 

Además, el triángulo de Pascal puede resolver este problema también:

        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
 

Tenga en cuenta que las soluciones para una cuadrícula 1x1 son 2, una cuadrícula 2x2 es 6 y una cuadrícula 3x3 es 20. Así, el número más alto para 40X40 es la respuesta para este problema! C # programa se puede escribir de la siguiente manera:

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