Home
📐

Pascal’s triangle

Following my previous post on the Fibonacci numbers, here's a quick post on generating another famous mathematical sequence - Pascal's Triangle. 
    1
   1 1
  1 2 1
 1 3 3 1
1 4 6 4 1

🔗 Quick Background

Pascal's triangle contains numbers formed by binomial coefficients (often referred to as "N choose K"), but there's a simple and elegant way to generate it: each item is the sum of the two numbers above it. 
 1 3 3 1
1 46 4 1
We see here that the underlined 6 is formed by adding the two threes above it. 
 1 3 3 1
14 6 41
Similarly, we see the 4 is formed by adding the 1 and 3, and the 1 is formed by adding 1 to nothing (0).

🔗 Summing pairs

Before we get started go ahead and grab yourself a copy of the J runtime if you haven't already.
Let's start by grabbing the first 5 integers using the "integers" verb i. 
  i. 5
0 1 2 3 4
We can use the "same" verb ] to echo whatever we pass into it. 
  ] 10
10
  ] i.5
0 1 2 3 4
Our primary tool will be J's infix adverb \. This single backslash allows us to scan through a list of numbers in groups and apply a function to them.
Let's scan every 3 items and pass them to the "same" verb ]. 
  3 ]\ i.5
0 1 2
1 2 3
2 3 4
We can see here that J looks through 0 1 2 3 4 in overlapping groups of 3. So we'll have 0 1 2, followed by 1 2 3, etc.
By changing the number in front, we can scan in groups of 2. 
  2 ]\ i.5
0 1
1 2
2 3
3 4
Let's swap out our boring ] for something more interesting: +/, which sums a list of numbers. 
  3 +/\ i.5
3 6 9
  +/ 0 1 2
3
  +/ 1 2 3
6
  +/ 2 3 4
9
Similarly, we can do this pairwise. 
  2 +/\ i.5
1 3 5 7
Pretty nifty right?

🔗 Row after row

So why is this useful? Well, if we take another look at our triangle: 
    1
   1 1
  1 2 1
 1 3 3 1
1 4 6 4 1
We can see that the next row, 1 5 10 10 5 1 can be formed by this exact strategy: summing each pair of numbers to generate the number beneath it. 
  2 +/\ 1 3 3 1
4 6 4
  2 +/\ 1 4 6 4 1
5 10 10 5
Well, almost. Our issue is that we're missing out on the 1s on either side! This is because our infix operator \ starts with +/ 1 4 to get 5 - skipping over the 1.
To fix this, let's surround our row with 0s. 
  2 ]\ 0 1 3 3 1 0
0 1
1 3
3 3
3 1
1 0
  2 +/\ 0 1 3 3 1 0
1 4 6 4 1
  2 +/\ 0 1 4 6 4 1 0
1 5 10 10 5 1
Much better. So how do we surround with 0s automatically?
The append verb , is used to join items and lists. 
  0 , 1
0 1
  1 2 3 , 7 8 9
1 2 3 7 8 9
The "bond" verb & allows us to partially evaluate a verb that normally expects items on both sides. 
  1 + 2
3
  (1&+) 2
3
  4 % 2    NB. "%" is division!
2
  (%&2) 4
2
We can bind our append verb to add a 0 to either side. 
  (0&,) 5 6 7
0 5 6 7
  (,&0) 5 6 7
5 6 7 0
We can also do both. 
  (0&,) (,&0) 5 6 7
0 5 6 7 0
  (,&0) (0&,) 5 6 7
0 5 6 7 0
Putting it all together: we can append 0 on either side of our row: 
  (0&,) (,&0) 1 4 6 4 1
0 1 4 6 4 1 0
And sum each pair: 
  2 +/\ (0&,) (,&0) 1 4 6 4 1
1 5 10 10 5 1

🔗 All together now

Let's wrap this in our own verb called next. "y" gives us access to the argument(s) passed in. 
  next =: verb : '2 +/\ (0&,) (,&0) y'
  next 1 3 3 1
1 4 6 4 1
  next 1 4 6 4 1
1 5 10 10 5 1
Fortunately, next works just fine on the first row of our triangle: a single 1. 
  next 1
1 1
We can apply next multiple times. 
  next 1
1 1
  next 1 1
1 2 1
  next next 1
1 2 1
  next next next next 1
1 4 6 4 1
We can use the "power" verb ^: to do this for us. 
  (next^:0) 1
1
  (next^:1) 1
1 1
  (next^:5) 1
1 5 10 10 5 1
We can also pass a list to ^: to generate multiple powers at the same time. 
  (next^:(i.7)) 1
1 0  0  0  0 0 0
1 1  0  0  0 0 0
1 2  1  0  0 0 0
1 3  3  1  0 0 0
1 4  6  4  1 0 0
1 5 10 10  5 1 0
1 6 15 20 15 6 1
We can store this as another verb to generate Pascal's Triangle. We’ll also simplify our definition of next using the "atop" verb @. 
  next =: 2 +/\ (0&,) @ (,&0)
  pascal =: verb : '(next^:(i.y)) 1'
  NB. We can also inline `next` entirely
  pascal =: verb : '((2 +/\ (0&,) @ (,&0))^:(i.y)) 1'
  pascal 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
🎉 🎉
Thanks to the powers of \ and ^:, we can intuitively generate Pascal's Triangle in a few dozen characters.
J makes operations on lists and matrices a breeze, and contains a number of interesting ideas for function composition and application. I hope you found this post interesting and give a look at what J has to offer.
I think you'll be pleasantly surprised at how fun it is.
Thanks for reading!