What computational shortcut finds the sum all possible products given any list of n random real numbers taken r at a time? Here's what I tried...

Question

I have the following computational shortcuts for any list of $n=4$ quantities taken r at a time. My goal is to do this for lists of any length. Taken r at a time, what function can similarly output sums of all possible products for sets of random quantities and beyond $n=4$ of them?

Here's the work I've done so far in Desmos: https://www.desmos.com/calculator/dvjyqf51gj

Please help. This only works for distinct quantities and for $n = 4$ of them.

I’m quite stumped to know what elegant function takes n random quantities as inputs and the sum of all possible products of these quantities taken r at a time as output.

So $F([n\ quantities], r)$ = sum of all possible products taken r at a time.

As example,

$F([5,4,3,2],1)=(5)+(4)+(3)+(2)=14$

$\ where\ n\ =\ 4\ and\ r=1$

$\sum_{i=1}^{n}x_{i}=14$

---

$F([5,4,3,2],2)=(5)(4)+(5)(3)+(5)(2)+(4)(3)+(4)(2)+(3)(2)=20+15+10+12+8+6=71$

$\ where\ n\ =\ 4\ and\ r=2$

$\left(\prod_{i=1}^{n}\left(1+x_{i}\right)\right)-\left(\prod_{i=1}^{n}x_{i}\right)\left(1+\sum_{i=1}^{n}1/x_{i}\right)-\left(\sum_{i=1}^{n}x_{i}\right)-1=71$

---

$F([5,4,3,2],3)=(5)(4)(3)+(5)(4)(2)+(5)(3)(2)+(4)(3)(2)=60+40+30+24=154$

$\ where\ n\ =\ 4\ and\ r=3$

$\left(\prod_{i=1}^{n}x_{i}\right)\sum_{i=1}^{n}1/x_{i}=154$

---

$F([5,4,3,2],4)=(5)(4)(3)(2)=120$

$\ where\ n\ =\ 4\ and\ r=4$

$\prod_{i=1}^{n}x_{i}=120$

---

Answer 1

We can let $x_1,\ldots, x_n$ to denote the $n$ random numbers. $$(x_1+x_2+\cdots+x_n)^r=\sum_{\substack{i_1,\ldots,i_r \\ \in \{1,\ldots,n\}}}x_{i_1}x_{i_2}\cdots x_{i_r}$$ In your problem, I guess you want $i_1,\ldots, i_r$ to be pairwise distinct. So, $$\sum_{\substack{i_1,\ldots,i_r\\ i_j\ne i_k \forall j, k}}x_{i_1}\cdots x_{i_r}=(x_1+\cdots+x_n)^r-\sum_{k=2}^{r}x_1^k(x_2+\cdots+x_n)^{r-k}$$ This formula also indicates that the sum of products can be calculated recursively in the number of terms per product. Is this what you were looking for?

Answer 2

As mentioned in https://stackoverflow.com/questions/9280936/efficient-algorithm-to-calculate-the-sum-of-all-k-products

Let $F(r,n)$ be the $r$-product sum of first $n$ elements $X$. $F(r,n) = F(r,n-1)+F(r-1,n-1)x_n$

The formula works because $F(r,n-1)$ contains the products not using $x_n$. The remaining terms can be factorized by $x_n$, and we get all the products on $r-1$ terms not using $x_n$. For example, with $r=3$ and $n=5$: $F(3, 5) = x_1x_2x_3 + x_1x_2x_4 + x_1x_2x_5 + x_1x_3x_4 + x_1x_3x_5 + x_1x_4x_5 + x_2x_3x_4 + x_2x_3x_5 + x_3x_4x_5 = (x_1x_2x_3 + x_1x_2x_4 + x_1x_3x_4 + x_2x_3x_4) + (x_1x_2x_5 + x_1x_3x_5 + x_1x_4x_5 + x_2x_3x_5 + x_3x_4x_5) = F(3, 4) + (x_1x_2 + x_1x_3 + x_1x_4 + x_2x_3 + x_3x_4)x_5 = F(3, 4) + F(2, 4)x_5$.

This can be computed efficiently by dynamic programming, which means you will compute $F(i, j)$ for all $0\leq i \leq r$, $0\leq j \leq n$. This will take a time of $\mathcal{O}(kn)$, which is far better than the exponential time when computing naively.

This formula is efficient for computing the sum, but it appears desmos does not have tools for recursivity (apparently, there are some tricks to do with one variables, but two is more complex). I suggest using another tool, or learning to code a little bit (that's not that hard).