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 , 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 , the (2n)-th binomial coefficients are the polynomial coefficients of , 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.