As the festive seasons is coming to a close and we've seen out all twelve days of Christmas I found myself thinking about the famous carroll of the same name. Namely, how many presents in total did my true love give to me? This is can be given by the nested summation
$\sum \limits_{i=1}^{12} (\sum \limits_{j=1}^i j)$ ,
where the inside sum is the number of presents received each day (i.e a partridge in a pear tree on the first day, two turtle doves and a partridge in a pear tree on the second day, etc.) and the outside summation sums over the days. This can be found to be 364, but what about in general for $n$ days of Christmas?
Well we can generalise the summation by just inserting $n$ into the summation and solving it.
$\sum \limits_{i=1}^{n} (\sum \limits_{j=1}^i j)$
Using the well known solution of the sum $~ \sum \limits_{i=1}^{n}i = \frac{n(n+1)}{2} ~$ we can obtain a non-nested sum,
$ = \sum \limits_{i=1}^{n} \frac{i(i+1)}{2} = \sum \limits_{i=1}^{n} (\frac{1}{2}i^2 + \frac{1}{2}i )$ ,
which we can split into separate summations
$ = \frac{1}{2} \sum \limits_{i=1}^{n} i^2 + \frac{1}{2}\sum \limits_{i=1}^{n}i = \frac{n(n+1)(2n+1)}{12}+ \frac{n(n+1)}{4} = \frac{n(n+1)(2n+1) + 3n(n+1)}{12} = \frac{2n^3 + 6n^2 + 4n}{12} = \frac{n(n+1)(n+2)}{6}$
which we notice can be written as the binomial coefficient,
$ = {n+2\choose3}$.
This doesn't really come as any surprise since this kind of problem seems like the prime candidate for one which could be solved using some fancy combinatorics to yield a binomial coefficient. But if we notice now that we can write the standard arithmetic series sum as a binomial coefficient, eg.,
$~ \sum \limits_{i=1}^{n}i = \frac{n(n+1)}{2} = {n+1\choose2} ~$
we might notice a similarity between them.
Similarly it can be shown that for a twice nested sum we have,
$\sum \limits_{i=1}^{n} (\sum \limits_{j=1}^i (\sum \limits_{k=1}^j k)) = {n+3\choose4} $.
In general it seems for an $(m-1)$-th nested sum (i.e, one which has $m$ summation symbols) we have,
$\sum \limits_{i_1=1}^{n} \sum \limits_{i_2=1}^{i_1} \sum \limits_{i_3=1}^{i_2} \dots \sum \limits_{i_m=1}^{i_{m-1}}i_m = {n+m\choose1+m} $
and this is likely provable with induction.
My question is to you is, how can this relationship between binomial coefficient and summations be thought of? That is to say, why would taking the number of possible pairs of $n+1$ elements happen to give you the sum from $1$ to $n$? And how does this somehow seem to extent with nested summations; the number of ways you can take 3 elements from $n+2$ gives you the first nested summation and so on? I'm sure some combinatorics whizz will be able to rearrange the way we count these sums somehow to yield the answer. Anyway at the very least it's interesting to think about - happy holidays!
Answer
Suppose you want number of non-negative integer solutions of the equation
$$x_1+\ldots+x_n = k+1$$
The answer is $\binom{k+n}{k+1}$ (a standard application of Stars and Bars).
Now, look at the case $k=1$ for simplicity. We construct a solution as follows: initialize each components of the vector $(x_1,\ldots, x_n)$ to zero, then to make their sum $2$, we add $1$ to one of the components at two steps one by one.
In the first step, we have $n$ choices where to add the $1$. Suppose we added it at the $i$-th position, i.e. $x_j=0$ unless $j\neq i$, and $x_i=1$ after this step.
At the next step, we add the second $1$ to the $j$-th position, imposing the condition $j\leq i$ to avoid having same solution twice.
We can do this in $\sum_{i=1}^n\sum_{j=1}^i1$ ways. Result using the formula must also be same, so
$$\binom{n+1}{2} = \sum_{i=1}^n\sum_{j=1}^i1$$
For higher values of $k$, we just need to remember where we add the first $1$ is rightmost, and for the next steps, tail of the vector will remain empty. Then the formulas are apparent.
No comments:
Post a Comment