On the nth day of Christmas…

Today PNC Wealth Management announced its Christmas Price Index. This is the cost of buying all the gifts in the song The Twelve Days of Christmas. All 364 of them.

Where’d that number come from? Well, there is one on the first day: a partridge in a pear tree. There are three gifts on the second day: two turtle doves, and a partridge in a pear tree. And so on up until 78 gifts on the twelfth day: twelve drummers drumming, eleven pipers piping, and all the way on down. The total number of gifts bought is 1 + 3 + 6 + … + 78 = 364, which is, coincidentally, one less than the number of days in the year. (The number 365, being just the nearest integer to a ratio of two times, can’t have any number-theoretic significance.)

But what if Christmas lasted n days instead of three? What then?

The identity 1 + 3 + 6 + \cdots + 78 = 364 is a special case of

{2 \choose 2} + {3 \choose 2} + \cdots + {n+1 \choose 2} = {n+2 \choose 3} $

which in turn is a special case of the “hockey-stick identity”

{k \choose k} + {k+1 \choose k} + \cdots + {m \choose k} = {m+1 \choose k+1} $

or in more compact notation

\sum_{j=k}^m {j \choose k} = {m+1 \choose k+1}.

Let’s prove this identity. We want to choose k+1 elements from the set \{ 0, 1, 2, \ldots, m \}. We can do this by first choosing the largest element, and then choosing the $k$ smaller elements. If we choose j to be the largest element, there will be {j \choose k} ways to pick the k smaller elements from \{ 0, 1, \ldots, k-1 \}; summing over the possible values of j gives the answer.

But a different way of counting is suggested by observing that over the 364 days, the true love receives:

  • 1 \times 12 = 12 partridges-in-pair-trees;
  • 2 \times 11 = 22 turtle doves;
  • 3 \times 10 = 30 french hens;
  • 12 \times 1 = 12 drummers drumming

and so we get the identity

1 \times 12 + 2 \times 11 + 3 \times 10 + \cdots + 12 \times 1 = 364.

If there’s anything right with the world, this ought to be a special case of

1 \times n + 2 \times (n-1) + 3 \times (n-2) + \cdots + n \times 1 = {n+2 \choose 3}

and why should this be? Let’s write this as

\sum_{j=2}^{n+1} (j-1) (n+2-j) = {n+2 \choose 3}

where the reason for the somewhat strange indexing will be apparent shortly.

Let’s count subsets of the set \{ 1, 2, \ldots, n+2 \} of size 3. We can write each such subset as \{ x, y, z \} where we require x < y < z. > Then we’ll count these subsets according to the difference z - x. To construct such a set with z - x = j we must:

  • choose x. x must be between 1 and n+2-j inclusive, so there are n+2-j possible choices.
  • choose y. y must be between x and z=x+j exclusive, so there are j-1 possible choices.

At this point z is fixed. So there are (j-1)(n+2-j) ways to choose the 3-set with z - x = j; summing over the possible values of j gives the answer.

(Is there a natural generaliztion of this later identity that counts sets of sizes 4 or larger?)

So by counting sets of size 3 in two different ways, we’ve made combinatorial proofs of two different identities, both with a binomial coefficient with “lower number” 3.

The 364-gift total has been observed in various places; people who have looked at the math instead of just adding up the numbers include Murray Bourne and Brent Yorgey. And Knuth observed that the song itself has a space complexity of O(\sqrt{n/(log n)}).

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s