Essays/Pascal's Triangle

Pascal's triangle is traditionally a triangular arrangement of the binomial coefficients.

                  1
                1   1
              1   2   1
            1   3   3   1
          1   4   6   4   1
        1   5  10   10  5   1
      1   6   15  20  15  6   1
    1   7  21  35   35  21   7  1
  1   8  28   56  70  56  28  8   1
1   9  36  84  126  126 84  36  9   1

In J it is more convenient to treat it as a table, and it is seen that Pascal's triangle is simply a table of the ! verb, the Taylor coefficients of the function $(x+1)^{n}$, or powers of the verb 0&, + ,&0 . The last has an interesting pedigree, being among the first J phrases ever written (APL\?, 1990, Appendix, Frame Gc) and among the first APL phrases ever written (APL\360 Terminal System, 1967, Figure 1).

   ] x=: !/~ i.10
1 1 1 1 1  1  1  1  1   1
0 1 2 3 4  5  6  7  8   9
0 0 1 3 6 10 15 21 28  36
0 0 0 1 4 10 20 35 56  84
0 0 0 0 1  5 15 35 70 126
0 0 0 0 0  1  6 21 56 126
0 0 0 0 0  0  1  7 28  84
0 0 0 0 0  0  0  1  8  36
0 0 0 0 0  0  0  0  1   9
0 0 0 0 0  0  0  0  0   1

   3 : '(y ^~ >:) t. i.1+y'"0 i. 10
1 0  0  0   0   0  0  0 0 0
1 1  0  0   0   0  0  0 0 0
1 2  1  0   0   0  0  0 0 0
1 3  3  1   0   0  0  0 0 0
1 4  6  4   1   0  0  0 0 0
1 5 10 10   5   1  0  0 0 0
1 6 15 20  15   6  1  0 0 0
1 7 21 35  35  21  7  1 0 0
1 8 28 56  70  56 28  8 1 0
1 9 36 84 126 126 84 36 9 1

   (0&, + ,&0)^:(i.10) 1
1 0  0  0   0   0  0  0 0 0
1 1  0  0   0   0  0  0 0 0
1 2  1  0   0   0  0  0 0 0
1 3  3  1   0   0  0  0 0 0
1 4  6  4   1   0  0  0 0 0
1 5 10 10   5   1  0  0 0 0
1 6 15 20  15   6  1  0 0 0
1 7 21 35  35  21  7  1 0 0
1 8 28 56  70  56 28  8 1 0
1 9 36 84 126 126 84 36 9 1

The second method leads to the following observation: Since the n-th set of binomial coefficients are the polynomial coefficients of $(x+1)^{n}$, the (2n)-th binomial coefficients are the polynomial coefficients of $(x+1)^{2n}$, which obtain efficiently by polynomial multiplication. Thus:

   polytimes=: +//.@(*/)
   polytimes~ 1 9 36 84 126 126 84 36 9 1
1 18 153 816 3060 8568 18564 31824 43758 48620 43758 31824 18564 8568 3060 816 153 18 1
   (i.19)!18
1 18 153 816 3060 8568 18564 31824 43758 48620 43758 31824 18564 8568 3060 816 153 18 1

Some interesting sums on the table of Pascal's triangle:

   x=: !/~ i.10

   +/ x
1 2 4 8 16 32 64 128 256 512

   1 , +/"1 x
1 10 45 120 210 252 210 120 45 10 1
   (i.11) ! 10
1 10 45 120 210 252 210 120 45 10 1

   0 , (#x) {. +//. x
0 1 1 2 3 5 8 13 21 34 55

Large Values in Pascal's Triangle

The ways shown here to generate Pascal's triangle potentially suffer from loss of precision for points on the triangle which are too large. Here we seen an illustration of this problem and a suggestion for dealing with it.

---

Contributed by Roger Hui.