Pascal's Triangle

We name each integer in Pascal's triangle Coeff because it is the coefficient in the expansion of (1+x)ⁿ.

For example, (1 + x)⁴ = x⁴ + 4x³ + 6x² + 4x + 1

When x=1, 2⁴ = (1 + 1)⁴ = 1⁴ + 4 * 1³ + 6 * 1² + 4 * 1 + 1 = 16

For (zero based) row n, the sum of the coefficients = 2ⁿ.

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.

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