# 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.

Programming - a skill for life!

Code and screenshot of TINYDemo