## Thursday, December 22, 2011

### The "N Days of Christmas" Solution

A few days ago in The "N Days of Christmas" Puzzle I asked if you could figure out how many gifts you receive in total for all twelve days (not just on the twelfth day) of the song "The Twelve Days of Christmas," and to find an elegant way to calculate the number of gifts you'd receive if the number of days is extended beyond twelve.

First we need to figure out how many gifts we receive on a given day. It is a cumulative song, so you receive one partridge in a pear tree on the first day, then on the second day you receive two turtle doves and another partridge in a pear tree, and so on for twelve days. So the sequence for each day is:

1
1 + 2 = 3
1 + 2 + 3 = 6
1 + 2 + 3 + 4 = 10
1 + 2 + 3 + 4 + 5 = 15
...

That's probably enough terms that you'll start to recognize a pattern is forming. Each number in the sequence is just the sum of the first n integers, which you may recognize as the triangle numbers. For a small number of days like 12 we can just continue adding terms to the sequence and have the answer in about a minute. We could look up the formula for the nth triangle number, but with a little bit of intuition we can come up with one ourselves. (When you write your own blog, you get to pretend you're a little bit smarter and less lazy than you really are.) Sometimes it helps to draw a picture like the following:

Notice that the circles form the same sequence that we're after. Also note that since the circles are arranged in a triangle we can calculate the total number of circles by multiplying the height of the enclosing rectangle (n) by the width (n + 1) and dividing by 2. This gives us the formula for the nth triangle number.

$T_n = \frac{n(n + 1)}{2}$

That only gives us the number of gifts on the last day though. We wanted to know the number of gifts on all days combined, and we wanted to know it for any number of days. So what we really want isn't the nth triangle number (the sum of the first n integers), but the sum of the first n triangle numbers. That's a formula that we can derive from what we already know.

$\sum_{k=1}^{n}\frac{k(k + 1)}{2}$

$\frac{1}{2}\sum_{k=1}^{n}k(k + 1)$

$\frac{1}{2}\sum_{k=1}^{n}(k^2 + k)$

$\frac{1}{2}\sum_{k=1}^{n}k^2 + \frac{1}{2}\sum_{k=1}^{n}k$

At this point we should take a moment to say out loud what the two terms in this equation mean in plain English. On the left we have one-half of the sum of the first n squares, and on the right we have one-half of the sum of the first n integers. We already found a formula for the sum of the first n integers, and it seems like there ought to be a similar formula for the sum of the first n squares. There is, and to save us some time I’ll just substitute it here1.

$\frac{1}{2}\frac{n (n + 1) (2n + 1)}{6} + \frac{1}{2}\frac{n (n + 1)}{2}$

$\frac{(n^2 + n)(2n + 1)}{12} + \frac{n(n + 1)}{4}$

$\frac{(2n^3 + 3n^2 + n)}{12} + \frac{(n^2 + n)}{4}$

$\frac{(2n^3 + 3n^2 + n)}{12} + \frac{(3n^2 + 3n)}{12}$

$\frac{(2n^3 + 6n^2 + 4n)}{12}$

$\frac{(n^3 + 3n^2 + 2n)}{6}$

$\frac{n(n^2 + 3n + 2)}{6}$

$\frac{n(n + 1)(n + 2)}{6}$

That gives us our formula for the sum of the first n triangle numbers, which is also known as a tetrahedral number. This is the number you get when you turn the first n triangles on their side and stack them in a pyramid.

So if we plug 12 into the formula above, we find out that in total there are

$\frac{12 \times 13 \times 14}{6} = 364$

total gifts given in the Twelve Days of Christmas.

Happy Holidays!

1 The sequence given by the sum of the first N squares is called the square pyramidal numbers.

Tim Kington said...

Well, sure, if you already know the formula for the sum of the first n squares, then it's easy :) I solved it this way: I knew it would be cubic, because it was going to be a sum of squares, so I wrote four simultaneous equations for the first four terms:

ax^3 + bx^2 + cx + d = sum
f(1) = 1 = a + b + c + d
f(2) = 4 = 8a + 4b + 2c + d
etc.

It's pretty easy to solve that way.

There are some other ways here:
http://www.trans4mind.com/personal_development/mathematics/series/sumNaturalSquares.htm
and here:
http://www.wikihow.com/Solve-Recurrence-Relations

Bill the Lizard said...

Tim,

That step is more of a leap now that you mention it. I'll edit in at least a link for explanation this evening. Thanks a lot for sending me such a great puzzle. I love stuff like this.

Daniël said...

If you look at the diagonals of Pascal's pyramid, you will see this:

First diagonal: 1, 1, 1, 1, ...
Second diagonal: 1, 2, 3, 4, ...
Third diagonal: 1, 3, 6, 10, ...
Fourth diagonal: 1, 4, 10, 20, ...

The fourth diagonal corresponds to the total number of presents at each day.

There exists a simple formula to calculate any given element of Pascal's pyramid. Where n is the row number and k is the column number:

n! / (k! * (n - k)!)

Since we want the fourth diagonal, k = 3. (counting starts at 0)

For the first day, n = 3, since the first 3 rows do not have a 4th column.

Second day -> n = 4
Third day -> n = 5
etc.

Hence the general formula for the number of presents is:

(n + 2)! / (3! * (n - 1)!) =
((n+2)*(n+1)*n)/6

James said...

Last night a friend asked me if there was an equation to figure out the number of presents in the 12 days of Christmas, and this is what I came up with:

T(d) = Sum(n(d+1-n)), {1,d}

T(d) = the total presents in d days
d = the total natural number of days (12)
n = the days from 1 to d, {1,d}

So if d = 12, then
T(12) = Sum(n(13-n)), {1,12}

Thoughts?