Logic behind finding out Pascal's Triangle

Question

I found a bit of code to obtain Pascal's triangle without using arrays or nCr in Java, given below:

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 the life of me I can't figure out how this bit of code generates the required number (next in the sequence) :

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

Could someone please explain the logic behind how the number is generated? I'm interested in understanding how the formula for the next bit of number is obtained, i.e., how num=num*(r-col)/col works! I'm also interested in finding out how to derive such a formula.

Answer 1

First of all a little bit of theory: Pascal's triangle consists of binomial coefficients, where the entry on the kth column of the nth row represents the coefficient of x^(n−k)y^k, which can be calculated using the formula (n choose k), i.e. n! / ((n - k)!k!). More details can be found on wiki.

Now let's look at the code.

num = num * (r - col) / col

Say we're now computing the value of num at the nth row and kth column. Before executing this line, num has the value of nth row and (k-1)th column, i.e.

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

and the new value of num should be:

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

And so to get the new value of num (from the num representing previous entry), we need to multiply it by (row # - col # + 1) and then divide by the column #.

This is exactly what the code is doing. In this line:

num = num * (r - col) / col

r is actually == (row # + 1), and col is col #.

p.s. Don't know how to format formula on stackoverflow yet. Need to clean up my answer once I figure out how to do so.