364 gifts

On Christmas Day I alluded to the fact that there are 364 gifts in the song “The Twelve Days of Christmas”. Is there a way to prove this that doesn’t require adding everything up?

As a reminder, on day k of Christmas (k = 1, 2, …, 12) the singer receives 1 of gift 1, 2 of gift 2, …, k of gift k. Christmas has 12 days. (Gift 1 is “a partridge in a pear tree”, gift 2 is “turtle doves”, and so on up to gift 12 which is “drummers drumming”, but this is irrelevant.)

So on day k there are total of 1 + 2 + \ldots + k gifts; this is k(k+1)/2 = {k+1 \choose 2}. The total number of gifts received is therefore

{2 \choose 2} + {3 \choose 2} + \cdots + {13 \choose 2}

and by the hockey-stick identity (sometimes also called the Christmas stocking identity) this is {14 \choose 3}. The identity can be proven by induction, but I prefer a combinatorial proof. Consider the subsets of \{1, 2, \ldots, 14\} of size 3 and group them according to their largest element. Then there are {k \choose 2} sets whose largest element is k+1, for each of k = 2, \ldots 13.

This suggests another identity – what if we group according to the middle element of the subset instead? For example, there are 5 × 8 = 40 3-subsets of [14] whose middle element is 6; each one has one element chosen from 1, 2, …, 5 and one element chosen from 7, 8, …, 14. More generally there are k(13-k) 3-subsets of [14] with middle element k. Thus we have

1 \times 12 + 2 \times 11 + 3 \times 10 + \cdots + 12 \times 1 = {14 \choose 3}.

In terms of the song, this is actually a natural way to count. k(13-k) is the number of gifts of type k, since such gifts get given on the last 13-k days – there are 12 total partridges in pear trees, 2 × 11 = 22 total turtle doves, 3 × 10 = 30 total calling birds, and so on until we get back down to 12 drummers drumming. (The most frequent gifts? 42 swans and 42 geese. Maybe that was the question.)

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s