Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
@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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.