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
n
th 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}$.