# Sum of products of all combinations?

We are given a list $S$ containing $n$ numbers $S=(s_1,\ldots, s_n)$. Let $S \choose k$ be the set of all possible $k$-combinations from $S$ (i.e. size $k$ subsets of $S$). We want to compute the following expression:

$$\sum_{A\in {S \choose k}} \prod_{x \in A} x$$

Is there an algorithm for this problem that works much better than the trivial one which goes over all subsets and computing and summing up all products?

-
It is very unclear what you mean, but maybe you are looking for this: en.wikipedia.org/wiki/Newton's_identities –  Sasho Nikolov Jun 18 '14 at 18:54
@Kaveh: I tried to edit the wording to clarify what I am looking for. This should be something rather basic math, I am sure. –  Alexander Galkin Jun 18 '14 at 19:38
@Kaveh: Great, thank you a lot!! –  Alexander Galkin Jun 18 '14 at 20:03
You are asking for an efficient way to evaluate a specific multivariate symmetric polynomial at a specific input. There's lots known about symmetric polynomials; that might help you find a good solution. –  D.W. Jun 18 '14 at 21:24
Sum of all nonempty subset products? Dynamic programming. SubSum(N) = $s_{n}$ * SubSum(N-1) + SubSum(N-1) + $s_{n}$ –  Chad Brewbaker Jun 21 '14 at 20:26

Consider the polynomial $p(t) = \prod_{i=1}^n (s_i t + 1)$. Then we want to compute the coefficient of $t^k$ in $p(t)$. We can compute $p(t)$ using fast polynomial multiplication and then output the coefficient of $t^k$.

Say, partition $n$ polynomials $s_i t + 1$ into pairs and multiply the product of polynomials in each pair (using the standard fast polynomial multiplication algorithm). Then divide the obtained $n/2$ polynomials into pairs, and compute the product in each pair. Repeat this step over and over until we get one polynomial. At each step we can get rid of terms of degree higher than $k$.

Also note that if $k$ is small, we can just use dynamic programming.

-

I guess the following trick is essentially "Newton's identities", but this seems a much more straightforward application to your question than what's on the wikipedia page. I've seen this mentioned on math.se before but don't know of a particular reference.

First, we write down the polynomial $$p(x) = \prod_{i=1}^n (x + s_i) .$$

By simply multiplying out this polynomial (efficiently! it is $n$ products of degree $\leq n$ polynomials), we can write it as $$p(x) = \sum_{j=1}^n \alpha_j x^j.$$ where $\alpha_j$ is the sum of all coefficients of $x^j$, that is, all possible products of $n-j$ of the $s_i$s. In particular, $$\alpha_{n-k} = \sum_{A \in {S \choose k}} \prod_{s \in A} s .$$

-
This is typically credited in the TCS literature to Ben-Or, viz. the private communication from Ben-Or to Nisan & Wigderson cited in "Lower bounds on arithmetic circuits via partial derivatives." –  Joshua Grochow Jun 18 '14 at 22:48