Логика позади выяснения треугольника Паскаля

Question

Я нашел немного кода для получения треугольника Паскаля без использования массивов или nCr в Java, приведенный ниже:

int maxRows = 6;
int r, num;
for (int i = 0; i <= maxRows; i++) 
{
    num = 1;
    r = i + 1;

    //pre-spacing
    for (int j = maxRows - i; j > 0; j--) 
    {
        System.out.print(" ");
    }

    for (int col = 0; col <= i; col++) 
    {
        if (col > 0) 
        {
            num = num * (r - col) / col;
        }
        System.out.print(num + " ");
    }
    System.out.println();
}

Для жизни я не могу понять, как этот бит кода генерирует требуемое число (следующее в последовательности):

    for (int col = 0; col <= i; col++) 
    {
        if (col > 0) 
        {
            num = num * (r - col) / col;
        }
        System.out.print(num + " ");
    }

Может кто-нибудь объяснить, почему стоит генерировать число? Мне интересно понять, как получается формула для следующего бита числа, т. Е. Как num=num*(r-col)/col работает! Мне также интересно узнать, как получить такую ​​формулу.

Answer 1

Прежде всего немного теории: треугольник Паскаля состоит из биномиальных коэффициентов, где запись в k-м столбце n-й строки представляет коэффициент x^(n−k)y^k, который можно вычислить по формуле (n выберите k), то есть n! / ((n - k)!k!). Более подробную информацию можно найти на вики.

Теперь давайте посмотрим на код.

num = num * (r - col) / col

Скажем, теперь мы вычисляем значение num в n-й строке и k-м столбце. Перед выполнением этой строки num имеет значение n-й строки и (k-1) -го столбца, т.е.

num == (n choose (k-1)) == n! / ((n - (k-1))!(k - 1)!)

и новое значение num должно быть:

    (n choose k) 
== n! / ((n - k)!k!) 
== (n! / ((n - (k-1))!(k - 1)!)) * (n - (k-1)) / k 
== num * (n - k + 1) / k

И поэтому, чтобы получить новое значение num (из num, представляющего предыдущую запись), нам нужно умножить его на (row # - col # + 1) и затем разделить на столбец #.

Это именно то, что делает код. В этой строке:

num = num * (r - col) / col

r на самом деле == (строка # + 1), а col это col #.

ps Пока не знаю, как форматировать формулу в stackru. Нужно очистить мой ответ, как только я пойму, как это сделать.