# How to calculate the sum

Is there any easy way to calculate $\sum_{a=0}^m \sum_{b=0}^m \sum_{c=0}^m \min_2(a,b,c)$ as a function of $m$ ?

$\min_2(a,b,c)$ is the second minimum of $a,b,c$. That is if $a \leq b \leq c$, $\min_2(a,b,c)=b$. $m$ is a positive integer.

Considering all different cases i.e,

$\sum_{a=0}^m \sum_{b=0}^a \sum_{c=0}^b,\sum_{a=0}^m \sum_{b=0}^a \sum_{c=b}^a, \sum_{a=0}^m \sum_{b=0}^a \sum_{c=a}^m,\\ \sum_{a=0}^m \sum_{b=a}^m \sum_{c=0}^a \sum_{a=0}^m \sum_{b=a}^m \sum_{c=a}^b, \sum_{a=0}^m \sum_{b=a}^m \sum_{c=b}^m$

desired sum can be calculated.

I want easier trick as I need also to calculate
$\sum_{a=0}^m \sum_{b=0}^m \sum_{c=0}^m\sum_{d=0}^m \min_3(a,b,c,d)$ and $\sum_{a=0}^m \sum_{b=0}^m \sum_{c=0}^m\sum_{d=0}^m \min_2(a,b,c,d)$.

-

Let $S=\{0,1,\ldots,m\}$; I’ll calculate the contribution of each $k\in S$ to the triple sum.

Fix $k\in S$; there are $k$ elements of $S$ less than $k$, and $m-k$ that are greater than $k$. Thus, there are $k(m-k)$ subsets of $S$ consisting of three distinct integers, of which $k$ is the middle one. Each of these subsets can be permuted in $3!=6$ ways, each of which contributes $k$ to the triple sum, for a total contribution of $6k^2(m-k)$.

There are $m$ $3$-element multisets in which $k$ appears twice along with some other element of $S$. Each can be permuted in $3$ distinguishable ways, so the total contribution of these multisets is $3km$.

Finally, the multiset consisting of three copies of $k$ contributes just $k$.

Altogether, then, $k$ contributes $6k^2(m-k)+3km+k$ to the triple sum, which is therefore

$$\sum_{k=0}^m\left(6k^2(m-k)+3km+k\right)=6m\sum_{k=0}^mk^2-6\sum_{k=0}^mk^3+(3m+1)\sum_{k=0}^mk\;.$$

We can now use some standard formulas to evaluate the three sums:

\begin{align*} &6m\sum_{k=0}^mk^2=6m\cdot\frac{m(m+1)(2m+1)}6=m^2(m+1)(2m+1)\;,\\ &6\sum_{k=0}^mk^3=6\left(\frac{m(m+1)}2\right)^2=\frac{3m^2(m+1)^2}2\;,\text{ and }\\ &(3m+1)\sum_{k=0}^mk=(3m+1)\cdot\frac{m(m+1)}2=\frac{m(m+1)(3m+1)}2\;. \end{align*}

I’ll leave the remaining simplication to you.

A similar analysis should take care of your other problems, though the details will be a bit messier.

Added: The sum actually works out to $\frac12m(m+1)^3$, which led me to wonder whether there was a nicer way to derive it. There is. For each $k\in S$ let $\bar k=m-k$. Then we can pair the triple $\langle a,b,c\rangle$ in the sum with the triple $\langle\bar a,\bar b,\bar c\rangle$; if $\langle a,b,c\rangle$ contributes $k=\min_2\{a,b,c\}$ to the sum, then $\langle\bar a,\bar b,\bar c\rangle$ contributes $\bar k$, so the two together contribute $k+\bar k=m$. If $m$ is odd, $\langle\bar a,\bar b,\bar c\rangle$ is never equal to $\langle a,b,c\rangle$, so no triple is counted twice. There are $(m+1)^3$ triples, so there are $\frac12(m+1)^3$ pairs of triples, each contributing $m$ to the sum for a total of $\frac12m(m+1)^3$. If $m$ is even, the triple $\left\langle\frac{m}2,\frac{m}2,\frac{m}2\right\rangle$ is paired with itself; it contributes $\frac{m}2$ to the sum. Apart from it, there are $\frac12\left((m+1)^3-1\right)$ pairs, each contributing $m$ to the sum, for a grand total of

$$\frac{m}2+\frac12m\left((m+1)^3-1\right)=\frac12m(m+1)^3\;,$$

as before.

It may be useful to note that in your quadruple sums, $\min_3\{a,b,c,d\}=\overline{\min_2\{\bar a,\bar b,\bar c,\bar d\}}$. As $\langle a,b,c,d\rangle$ runs over all $(m+1)^4$ possible quadrupose, so does $\langle\bar a,\bar b,\bar c,\bar d\rangle$. Thus, the $\min_3$ sum is obtained by replacing each term $k$ in the $\min_2$ sum by $\bar k$. Each sum has $(m+1)^4$ terms, so if $S_3$ and $S_2$ are the $\min_3$ and $\min_2$ sums, respectively, then $S_3=m(m+1)^4-S_2$: getting either sum gets you the other.

-
@user12290: I just checked it by hand for $m=3$; it gives the correct total and the correct subtotals. –  Brian M. Scott Aug 18 '13 at 6:11
Thank you very much. –  user12290 Aug 18 '13 at 13:35
@user12290: You’re very welcome. I just added some afterthoughts that may help to reduce the work a little on the extended part of the problem. –  Brian M. Scott Aug 18 '13 at 17:34