Pascal matrix generation

Pascal matrix generation is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

A pascal matrix is a two-dimensional square matrix holding numbers from Pascal's triangle, also known as binomial coefficients and which can be shown as ⁿC_r.

Showing truncated 5-by-5 matrices M[i, j] for i,j in range 0..4.
A Pascal upper-triangular matrix is populated with ^jC_i

[[1, 1, 1, 1, 1],
 [0, 1, 2, 3, 4],
 [0, 0, 1, 3, 6],
 [0, 0, 0, 1, 4],
 [0, 0, 0, 0, 1]]

A Pascal lower-triangular matrix is populated with ⁱC_j (the transpose of the upper-triangular matrix).

[[1, 0, 0, 0, 0],
 [1, 1, 0, 0, 0],
 [1, 2, 1, 0, 0],
 [1, 3, 3, 1, 0],
 [1, 4, 6, 4, 1]]

A Pascal symmetric matrix is populated with ^i+jC_i

[[1, 1, 1, 1, 1],
 [1, 2, 3, 4, 5],
 [1, 3, 6, 10, 15],
 [1, 4, 10, 20, 35],
 [1, 5, 15, 35, 70]]

The task is to write functions capable of generating each of the three forms of n-by-n matrices.
Use those functions to display upper, lower, and symmetric Pascal 5-by-5 matrices on this page. The output should distinguish between different matrices and the rows of each matrix (No showing a list of 25 numbers assuming the reader should split it into rows).

Note

1. The Cholesky decomposition of a Pascal symmetric matrix is the Pascal lower-triangle matrix of the same size.

Common Lisp

<lang lisp>(defun pascal-lower (n &aux (a (make-array (list n n) :initial-element 0)))

   (setf (aref a 0 0) 1)
   (loop for i from 1 below n do
       (setf (aref a i 0) 1)
       (loop for j from 1 below n do
           (setf (aref a i j)
               (+ (aref a (1- i) j)
                  (aref a (1- i) (1- j)))))
       finally (return a)))

(defun pascal-upper (n &aux (a (make-array (list n n) :initial-element 0)))

   (setf (aref a 0 0) 1)
   (loop for i from 1 below n do
       (setf (aref a 0 i) 1)
       (loop for j from 1 below n do
           (setf (aref a j i)
               (+ (aref a j (1- i))
                  (aref a (1- j) (1- i)))))
       finally (return a)))

(defun pascal-symmetric (n &aux (a (make-array (list n n) :initial-element 0)))

   (loop for i below n do
       (setf (aref a i 0) 1 (aref a 0 i) 1))
   (loop for i from 1 below n do
       (loop for j from 1 below n do
           (setf (aref a i j)
               (+ (aref a (1- i) j)
                  (aref a i (1- j)))))
       finally (return a)))

? (pascal-lower 4)

1. 2A((1 0 0 0) (1 1 0 0) (1 2 1 0) (1 3 3 1))

? (pascal-upper 4)

1. 2A((1 1 1 1) (0 1 2 3) (0 0 1 3) (0 0 0 1))

? (pascal-symmetric 4)

1. 2A((1 1 1 1) (1 2 3 4) (1 3 6 10) (1 4 10 20))</lang>

J

<lang J>  !/~ i. 5 1 1 1 1 1 0 1 2 3 4 0 0 1 3 6 0 0 0 1 4 0 0 0 0 1

  !~/~ i. 5

1 0 0 0 0 1 1 0 0 0 1 2 1 0 0 1 3 3 1 0 1 4 6 4 1

  (["0/!+/)~ i. 5

1 1 1 1 1 1 2 3 4 5 1 3 6 10 15 1 4 10 20 35 1 5 15 35 70</lang>

Explanation:

x!y is the number of ways of picking x balls (unordered) from a bag of y balls and x!/y for list x and list y gives a table where rows correspond to the elements of x and the columns correspond to the elements of y. Meanwhile !/~y is equivalent to y!/y (and i.y just counts the first y non-negative integers).

Also, x!~y is y!x (and the second example otherwise follows the same pattern as the first example.

For the final example we use an unadorned ! but prepare tables for its x and y values. Its right argument is a sum table, and its left argument is a left identity table. They look like this:

<lang J> (+/)~ i. 5 0 1 2 3 4 1 2 3 4 5 2 3 4 5 6 3 4 5 6 7 4 5 6 7 8

  (["0/)~ i. 5

0 0 0 0 0 1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 4 4 4 4 4</lang>

The parenthesis in these last two examples are redundant - they could have been omitted without changing the result, but were left in place for emphasis.

Perl 6

Here is a rather more general solution than required. The grow-matrix function will grow any N by N matrix into an N+1 x N+1 matrix, using any function of the three leftward/upward neighbors, here labelled "West", "North", and "Northwest". We then define three iterator functions that can grow Pascal matrices, and use those iterators to define three constants, each of which is an infinite sequence of ever-larger Pascal matrices. Normal subscripting then pulls out the ones of the specified size. <lang perl6># Extend a matrix in 2 dimensions based on 3 neighbors. sub grow-matrix(@matrix, &func) {

   my @m = @matrix.deepmap: { .clone }
   my $s = +@m; #     West          North         NorthWest
   @m[$s][0]  = func( 0,            @m[$s-1][0],  0             );
   @m[0][$s]  = func( @m[0][$s-1],  0,            0             );
   @m[$_][$s] = func( @m[$_][$s-1], @m[$_-1][$s], @m[$_-1][$s-1]) for 1 ..^ $s;
   @m[$s][$_] = func( @m[$s][$_-1], @m[$s-1][$_], @m[$s-1][$_-1]) for 1 .. $s;
   [@m];

}

1. I am but mad north-northwest...

sub madd-n-nw($m) { grow-matrix $m, -> $w, $n, $nw { $n + $nw } } sub madd-w-nw($m) { grow-matrix $m, -> $w, $n, $nw { $w + $nw } } sub madd-w-n ($m) { grow-matrix $m, -> $w, $n, $nw { $w + $n } }

1. Define 3 infinite sequences of Pascal matrices.

constant upper-tri := 1, &madd-w-nw ... *; constant lower-tri := 1, &madd-n-nw ... *; constant symmetric := 1, &madd-w-n ... *;

1. Pull out the 4th element of each sequence.

.say for upper-tri[4][]; say ; .say for lower-tri[4][]; say ; .say for symmetric[4][];</lang>

Output:

1 1 1 1 1
0 1 2 3 4
0 0 1 3 6
0 0 0 1 4
0 0 0 0 1

1 0 0 0 0
1 1 0 0 0
1 2 1 0 0
1 3 3 1 0
1 4 6 4 1

1 1 1 1 1
1 2 3 4 5
1 3 6 10 15
1 4 10 20 35
1 5 15 35 70

Python

Python: Summing adjacent values

<lang python>from pprint import pprint as pp

def pascal_upp(n):

   s = [[0] * n for _ in range(n)]
   s[0] = [1] * n
   for i in range(1, n):
       for j in range(i, n):
           s[i][j] = s[i-1][j-1] + s[i][j-1]
   return s

def pascal_low(n):

   # transpose of pascal_upp(n)
   return [list(x) for x in zip(*pascal_upp(n))]

def pascal_sym(n):

   s = [[1] * n for _ in range(n)]
   for i in range(1, n):
       for j in range(1, n):
           s[i][j] = s[i-1][j] + s[i][j-1]
   return s
   

if __name__ == "__main__":

   n = 5
   print("\nUpper:")
   pp(pascal_upp(n))
   print("\nLower:")
   pp(pascal_low(n))
   print("\nSymmetric:")
   pp(pascal_sym(n))</lang>

Output:

Upper:
[[1, 1, 1, 1, 1],
 [0, 1, 2, 3, 4],
 [0, 0, 1, 3, 6],
 [0, 0, 0, 1, 4],
 [0, 0, 0, 0, 1]]

Lower:
[[1, 0, 0, 0, 0],
 [1, 1, 0, 0, 0],
 [1, 2, 1, 0, 0],
 [1, 3, 3, 1, 0],
 [1, 4, 6, 4, 1]]

Symmetric:
[[1, 1, 1, 1, 1],
 [1, 2, 3, 4, 5],
 [1, 3, 6, 10, 15],
 [1, 4, 10, 20, 35],
 [1, 5, 15, 35, 70]]

Python: Using a binomial coefficient generator function

<lang python>def binomialCoeff(n, k):

   result = 1
   for i in range(1, k+1):
       result = result * (n-i+1) // i
   return result

def pascal_upp(n):

   return [[binomialCoeff(j, i) for j in range(n)] for i in range(n)]

def pascal_low(n):

   return [[binomialCoeff(i, j) for j in range(n)] for i in range(n)]

def pascal_sym(n):

   return [[binomialCoeff(i+j, i) for j in range(n)] for i in range(n)]</lang>

Output:

(As above)