# 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} = x^{4} + 4x^{3} + 6x^{2} + 4x + 1

When x=1, 2^{4} = (1 + 1)^{4} = 1^{4} + 4 * 1^{3} + 6 * 1^{2} + 4 * 1 + 1 = 16

^{n}.

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 2^{n}, and invite you to do the same. If you output the row totals you will see the familiar powers of two such as 2^{16} = 65536.