(Edit, 12/5/07: I guess it’s that time of year again, isn’t it? =) I’ve started to see a lot more traffic to this post in the last few days. For anyone finding me through a Google search, I wanted to note that this was actually the first post in a seven-part series, and you can read the rest of the series here: computing tetrahedral numbers, triangular numbers, binomial coefficients,
a solution to the triangular number challenge, pascal’s triangle, and the conclusion tying everything together.)
“On the first day of Christmas, my true love gave to me…“
Thus the opening words to the popular Christmas song. In case you don’t know it (hey, it’s possible), it concerns an individual who recounts, in obsessive detail, a catalogue of gifts received from their “true love”. It is a matter of some speculation whether the “true love” bit is intended as sarcasm, for reasons we shall soon see. At any rate, on each of the twelve days of Christmas the “true love” gives the narrator all the same gifts as on the previous day, plus a new gift item in a quantity determined by the number of days since the start of Christmas. For example, on the fifth day, the narrator receives five golden rings, four calling birds, three french hens, two turtle doves, and a partridge in a pear tree. (Or five onion rings, four calling cards, three french fries, two turtle necks, and an MC Hammer CD, depending on which version of the song you know.) This song raises several interesting questions, including “What the heck is a turtle dove?” and “Who does that?” More to the point of this post, however, it also raises the question, “So, how many gifts IS that!?”
Good question, I’m glad you asked! Let’s start by thinking about how many gifts are given on each day. On the first day, the narrator receives one gift: a partridge in a pear tree. On the second day, the narrator receives two turtle doves and a partridge in a pear tree: 2 + 1 = 3 gifts in total. On the third day, there are 3 + 2 + 1 = 6 gifts, on the fourth day, 4 + 3 + 2 + 1 = 10 gifts, and so on. In general, it’s not hard to see that on the nth day, the narrator receives a number of gifts equal to the sum of all the integers from 1 to n. So the number of gifts the narrator gets on each day are 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78.
These numbers are known as triangular numbers, due to the fact that they can be represented pictorially by dots arranged in triangles. Like this:
It shouldn’t be too hard to see that the number of dots in the nth triangle above corresponds to the sum of the integers from 1 through n (just count the number of dots in each row). Can you find a pattern and come up with a way to quickly figure out the nth triangular number, without having to add up all the numbers from 1 to n? (More on this in the next post.)
Of course, we’re not ultimately interested in how many gifts the narrator received on each day by itself; we want to know how many gifts the narrator got in total. Well, after the first day the narrator had one gift; after the second day, 1 + 3 = 4 gifts; after the third day, 1 + 3 + 6 = 10 gifts; and so on. In general, the total number of gifts after the nth day is just the sum of the first n triangular numbers: 1, 4, 10, 20, 35, 56, 84, 120, 165, 220, 286, 364.
These are known as tetrahedral numbers, since they can be represented pictorially by dots arranged in tetrahedra (i.e., triangular pyramids). Like this:
Do you see why? Each “layer” of a tetrahedron is a triangle of dots representing a triangular number: hence each tetrahedron is a sum of triangular numbers. The twelfth tetrahedral number, 364, tells us how many gifts our narrator received in total. 364 gifts is a lot. And with all those geese running around laying eggs everywhere, the continual racket from the drummers, and so on, I’m not sure I’d really want them.
So, we’ve learned about triangular numbers and tetrahedral numbers, and that the total number of gifts received by the narrator of the song corresponds to a tetrahedral number. But what if there were 144 days in Christmas instead of 12? How many gifts would our intrepid narrator receive then? Easy, you say, it’s the 144th tetrahedral number! Well, true, but what is that number? We don’t yet know a quick way to figure that out other than just adding everything up — but for a number as big as 144 that would be incredibly tedious (not to mention that we’d probably make a mistake). It turns out there is a quick way to figure it out — but that will have to wait for the next post!