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.)