How to find the average value/sum of combinations with repetitions

Question

Let's say I have a set $\{1, 2, ...x\}$ and pick every distinct combination of length 3 (including repeated numbers) and create a new set by adding values equal to the product of the elements in each combination. For example, if x = 4 the new set would be:

$$\{1*1*1, \ 2*1*1, \ 2*1*2, \ 2*2*2,\ 3*1*1,\ ... \ , 4*4*3, \ 4*4*4\}$$

These combinations are unique (that is, no value in the new set is repeated).

My goal is to find the sum of these values in terms of $x$. I already know the size of the new set in terms of $x$ which is why I ask for the average value (unless finding the sum is easier without the average and size).

Hopefully my explanation of the set was clear but if needed I can elaborate more.

Thank you kindly!

Answer 1

Here is a little different approach. I will write $n$ instead of $x$ as the variable. It's silly, but I can't get used to $x$ being an integer variable.

We seek to evaluate $T=T_1+T_2+T_3,$ where $$\begin{align} T_3&=\sum_{i=1}^n{i^3}\\ T_2&=\sum_{i=1}^n\sum_{j=1\\j\ne i}^n{ij^2}\\ T_1&=\sum_{i=1}^{n-2}\sum_{j=i+1}^{n-1}\sum_{k=k+1}^n{ijk} \end{align}$$ We will use the following well-known formulas: $$\begin{align} S_3&=\sum_{i=1}^n{i^3}={n^2(n+1)^2\over4}\\ S_2&=\sum_{i=1}^n{i^2}={n(n+1)(2n+1)\over6}\\ S_1&=\sum_{i=1}^n{i}={n(n+1)\over2} \end{align}$$ Note first that $$T_3=S_3\tag{1}$$ Then $T_2=(1^2+2^2+\cdots+n^2)(1+2+\cdots+n)-(1^3+2^3+\cdots+n^3).$ That is, $$T_2=S_2S_1-S_3\tag{2}$$ To compute $T_1,$ note that in the expression $(1+2+3+\cdots+n)^3,$ each term of $T_3$ occurs once, each term of $T_2$ occurs $3$ times, and each term of $T_1$ occurs $6$ times so that $$\begin{align} S_1^3 &= T_3+3T_2+6T_1\\ T_1&={S_1^3-T_3-3T_2\over6}=\\ &={S_1^3-S_3-3S_2S_1+3S_3\over6}=\\ &={S_1^3-3S_2S_1+2S_3\over6}\tag{3} \end{align}$$ using $(1)$ and $(2)$. Now, using $(1),(2),\text{ and }(3),$ we get $$T={S_1^3+3S_2S_1+2S_3\over6},$$ and substituting the formulas for $S_1,S_2,S_3$ and slogging through the algebra gives $$T=\boxed{{n^2(n+1)^2(n+2)(n+3)\over48}={n+1\choose2}{n+3\choose4}}$$ Sanity check: $n=2$ gives ${3\choose2}{5\choose4}=3\cdot5=15,$ in agreement with your calculation.

Answer 2

Using saulspatz's advice, I found that the sum of the terms in the new set of size $x$ is equivalent to:

$$(1 + \cdots + x)^3 - (1 + \cdots + x)(2 + 3(1+2) + \cdots + x(1 + \cdots + x))$$ $$= \left( \sum_{i=0}^xi \right) *\left[ \left( \sum_{i=0}^xi \right)^2 - \sum_{i=1}^x i *\left(\sum_{j=0}^i j \right) \right]$$

While I offer my gratitude to saulspatz for his/her help I do wonder if this could be expressed more simply.

Edit: I included a picture of an example of $x = 4$ to show this equivalency, where $S_A$ is the sum of the terms in the new set (what we are trying to find).