How many total gifts in the twelve days of christmas if we extend 12 to any number?

  • On the first day, you get 1.
  • On the second day, you get 1 + 2.
  • On the third day, you get 1 + 2 + 3.
  • ...
  • On nth day, you get 1 + 2 + 3 + ... + n.

The sum 1 + 2 + ... + n is n(n+1)/2. So the total number, T(N) is the sum of n(n+1)/2 for n in 1..N, where N is the number of days.

Now, n(n+1)/2 = n^2 / 2 + n / 2, and sum of n^2 for n in 1..N is N(N+1)(2N+1)/6, so you get:

T(N) = N(N+1)(2N+1)/12 + N(N+1)/4
     = N(N^2 + 3N + 2) / 6

No loops. No recursion.


The $P$-th type of present (where the $1$st is partridges, the $2$nd is turtle doves, etc.) comes in quantities of $P = \sum_{X = 1}^{P} 1$.

On day $D$, you receive presents of type $1$ through $D$, for a total of $\sum_{P = 1}^{D} \sum_{X = 1}^{P} 1$ many presents on that day.

And so, if the days run from $1$ through $N$ (canonically, $N$ is 12, but our interest now is in allowing it to vary), you receive overall $\sum_{D = 1}^{N} \sum_{P = 1}^{D} \sum_{X = 1}^{P} 1$.

This counts the number of non-decreasing triples $1 \leq X \leq P \leq D \leq N$.

This is the same as the number of increasing triples $1 \leq X < P + 1 < D + 2 \leq N + 2$.

So the answer is $\binom{N + 2}{3} = \frac{(N + 2)(N + 1)N}{6}$.

Tags:

Algorithm