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

---

Contributed by Roger Hui.