Pascal's Triangle

Pascal's Triangle
We name each integer in Pascal's triangle Coeff because it is the coefficient in the expansion of (1+x)n.
For example, (1 + x)4 = x4 + 4x3 + 6x2 + 4x + 1
When x=1, 24 = (1 + 1)4 = 14 + 4 * 13 + 6 * 12 + 4 * 1 + 1 = 16
For (zero based) row n, the sum of the coefficients = 2n.program PascalTriangle var Result, n, k, i, Coeff, nFact, kFact, subnkFact { Factorial by recursion, leaving the factorial in Result. } procedure Fact(Num) begin if Num = 0 Result = 1 else Fact(Num - 1) Result = Result * Num endIf end procedure PrintSpaces(n) var i begin for i = 1 n write(' ') endFor end begin writeLn() for n = 0 12 PrintSpaces(30 - n * 2) for k = 0 n if (k = 0) | (k = n) Coeff = 1 else Fact(n) nFact = Result Fact(k) kFact = Result Fact(n - k) subnkFact = Result Coeff = nFact/kFact / subnkFact endIf write(Coeff, ' ') if Coeff / 100 < 1 write(' ') endIf if Coeff / 10 < 1 write(' ') endIf endFor writeLn() endFor writeLn() writeLn() end
In this straightforward method we encounter overflow errors when calculating n! when n > 12.
Pascal's triangle by a better method
Rolfe's method for calculating binomial coefficients uses this recurrence relationship:
Coeff(n, k) = Coeff(n - 1, k - 1) * n / k
where both n (the row number) and k (the position in the row) are zero-based. Rolfe explains that the "alternating multiplication and division given through the recurrence relationship." avoids the extended precision arithmetic that would be necessary for the separate calculation of the numerator and denominator. In our first method we would have needed extended precision arithmetic for n > 12. Our implementation of the relationship is in the recursive procedure Coefficient in the code below. The following is a screenshot of part of the table. This time the rows are left-aligned. Notice the coefficients 1001, 2002, 3003, 5005 and 8008 which allow us to inspect at a glance the diagonal relationship.

Part of Pascal's Triangle
program PascalTriangle2 var MAX, Result, n, k, i, Coeff, Divisor { Factorial by recursion, leaving the factorial in Result. } procedure Fact(Num) begin if Num = 0 Result = 1 else Fact(Num - 1) Result = Result * Num endIf end { Recursive procedure for coefficient suggested by Rolfe } procedure Coefficient(n, k) begin Result = 1 if (k = 0) | (k = n) Coeff = 1 else Coefficient(n - 1, k - 1) Result = Result * n / k endif end begin MAX = 22 writeLn() for n = 0 MAX for k = 0 n if (k = 0) | (k = n) Coeff = 1 else Coefficient(n, k) Coeff = Result endIf write(Coeff, ' ') Divisor = 100000 while Divisor >= 10 if Coeff / Divisor < 1 write(' ') endIf Divisor = Divisor / 10 endWhile endFor writeLn() endFor writeLn() writeLn() end
We wrote further code to confirm that for each row of the table, the sum of the coefficients is equal to 2n, and invite you to do the same. If you output the row totals you will see the familiar powers of two such as 216 = 65536.