April 2025
A little while ago, I came across a description of an identity about elements of Pascal’s triangle. The identity seems to sometimes be called the “hockey-stick identity”, and sometimes the “Christmas stocking identity”. It says, roughly speaking, that the sum down a diagonal of Pascal’s triangle is equal to the entry in the next row and one “across” diagonally.
To give a concrete example:
| 1 | ||||||||
| 1 | 1 | |||||||
| 1 | 2 | 1 | ||||||
| 1 | 3 | 3 | 1 | |||||
| 1 | 4 | 6 | 4 | 1 |
Here, the blue diagonal entries, 1, 2, and 3, add up to the yellow entry, 6.
In general, suppose n and r are integers, with n ≥ r ≥ 0. Then, using the notation C(m, k) for binomial coefficients, the theorem says that
C(r, r) + C(r+1, r) + C(r+2, r) + ⋯ + C(n, r) = C(n+1, r+1).
This example is
C(1, 1) + C(2, 1) + C(3, 1) = C(4, 2),
and for small r, the identity can be loosely paraphrased as
The Wikipedia page has some proofs.
Knowing that this identity had a name, I was reminded of two examples I had encountered.
The first example is particularly apt given the “Christmas stocking” name. The task is to count the total number of gifts in the Twelve Days of Christmas song.
We can start with looking at the first few days:
Generalising this, on day n, the number of presents is the nth triangular number, which is C(n+1, 2).
To find the total number of presents over the twelve days of the song, we want the sum of the first twelve triangular numbers:
C(2, 2) + C(3, 2) + C(4, 2) + ⋯ + C(13, 2).
By the Christmas stocking identity, this is C(14, 3) = 364, which we can verify directly.
With combinatorial identities like this, it is interesting to see whether we can find an actual bijection. (A different example I wrote about previously is a bijection between expressions for integers as sums of square and triangular numbers.)
In this case, we want a bijection between these two sets:
For the second set, we can stack fourteen rows in a column, and imagine choosing three of them. Then a particular individual present can be identified as follows. The top chosen row determines the day; the middle chosen row tells us the kind of gift; and the bottom chosen row tells us the individual instance of that kind of gift on that day.
Below is an interactive illustration which lets you choose three things from fourteen by moving three sliders up and down. The fourteen rows are labelled such that the windows in the sliders combine to reveal each of the 364 individual presents. This does mean that each row of this table seems to be off by one day, but if you read what’s shown through the windows, everything works.
On the
day, my true love gave to me
Count them….
The other example is from a cool juggling show I saw at the 2024 European Juggling Convention. The show is called “Pyramid”, and the performer, Domenyk La Terra, did various elegant and skillful things with different numbers of balls, juggling them and balancing them on and rolling them along beams. I thought this was a very good show — worth seeing if you get the chance.
A big theme of the show (as you can guess from its title) is pyramids, and he works with different sizes of pyramids of juggling balls:
One part (and this is in the trailer, so is no more of a spoiler than if you watched the video on the performer’s site) involves combining these four pyramids of balls into one very big (5-layer) pyramid consisting of 35 balls.
My immediate thought when I saw this was that it was just a pleasing cosmic coincidence, but in fact it’s another instance of the hockey-stick identity, with one small extra step. By the hockey-stick identity, we can find the sum of the first four pyramid numbers (i.e., the total number of balls in the four pyramids) as follows:
C(3, 3) + C(4, 3) + C(5, 3) + C(6, 3) = C(7, 4) = 35.
But also, C(7, 4) = C(7, 3), because choosing four things you want from a tray of seven things is the same as choosing which three to leave on the tray, and C(7, 3) is the fifth pyramid number. So the sum of the first four pyramid numbers is the fifth pyramid number.
This observation will extend so that, for example,
C(4, 4) + C(5, 4) + C(6, 4) + C(7, 4) + C(8, 4) = C(9, 5) = C(9, 4),
which is saying that the first five hyper-pyramid numbers (if that is indeed their name) sum to the sixth:
1 + 5 + 15 + 35 + 70 = 126.
Going in the other direction, the sum of the first three triangular numbers is the fourth triangular number: 1 + 3 + 6 = 10, and the sum of the first two counting numbers is the third counting number: 1 + 2 = 3. We could even say that the sum of the first one one is the second one: 1 = 1.