# What's the sum of elements of this multi-set?

Let S be a $$\mathbf{multi}$$ set of integers such that:

$$S = \left \{\min(\mathbf{C}, a + b - 1) | a \in \left [ \mathbf{A} \right ], b \in \left [ \mathbf{B} \right ] \right \}$$

• Note that $$\mathbf{A}$$, $$\mathbf{B}$$ and $$\mathbf{C}$$ are positive integers and we know $$\mathbf{A} \leq \mathbf{B} \leq \mathbf{C}$$

• Also $$\left [ x \right ]$$ stands for $$\left \{ 1, 2, 3, \cdots , x \right \}$$

Can you figure out sum of all S elements using $$\mathbf{A}$$, $$\mathbf{B}$$ and $$\mathbf{C}$$ as parameters?

If $$C \ge A+B-1$$, then the min against $$C$$ will have no effect and the sum just reduces to $$\sum_{a=1}^A \sum_{b=1}^B (a + b - 1) = BA(A+1)/2 + AB(B+1)/2 - AB = AB(A+B)/2.$$

Let’s assume now that $$A \le B \le C < A+B-1$$. Then some of the values $$a+b-1$$ get replaced by the smaller $$C$$, so we just need to add up the deficits and subtract this from the previous total $$AB(A+B)/2$$.

It’s not hard to see that there is one value with maximum deficit $$A+B-C-1$$, two values with the next highest deficit $$A+B-C-2$$, etc., down to the minimum possible deficit of $$1$$ which occurs $$A+B-C-1$$ times (note that the assumption $$A,B\le C$$ is essential here, otherwise our count would be too high). The total deficit is thus simply $$f(A+B-C)$$, where

$$f(n) =\sum_{k=1}^n k(n-k) = (n^3-n)/6.$$

So the sum of the multi set $$S$$ is:

$$\tfrac12 AB(A+B) - \tfrac16 ((A+B-C)^3 - (A+B-C)),$$

unless $$A+B-C < 0$$, in which case you can discard the second term.

• Thanks! By the way, can you explain a bit more why the $A,B\le C$ assumption is essential? – CompuPhysics Mar 5 '20 at 5:33
• @CompuPhysics If you count the multiplicities of each value of $r=a+b-1$ you’ll find (assuming $A\le B$) there are $r$ copies of the value $r$ when $r \in [1,A]$; $A$ copies when $r \in [A,B]$; and $A+B-r$ copies when $r\in [B,A+B-1]$. The assumption $B\le C$ ensures that $C$ lies in the third interval and not in the first two intervals, which would affect the way we count. – Erick Wong Mar 5 '20 at 5:39