# J Notes — 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 4 6 4 1`

We see here that the bold 6 is formed by adding the two threes above it.

` 1 3 3 1  1 4 6 4 1`

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 — and feel free to give me a follow on twitter dot com for more J goodness.

Originally published at thatjdanisso.cool.

JavaScript clickbait enthusiast. Giving you superpowers.

## More from Jordan Scales

JavaScript clickbait enthusiast. Giving you superpowers.

## What You Need to Know About Binary Search in Javascript

Get the Medium app