<p>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.</p>

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

<p>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 .$$</p>

CC BY-SA 3.0
2014-06-18T22:48:00.897Z
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
CC BY-SA 3.0
2014-06-18T21:35:49.693Z
2014-06-18T21:35:49.693Z
usul
<p>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$. </p>

<p>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$.</p>

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

CC BY-SA 3.0
2014-06-18T21:38:40.180Z
2014-06-18T21:38:40.180Z
Yury
<p>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:</p>

<p>$$ \sum_{A\in {S \choose k}} \prod_{x \in A} x$$</p>

<p>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?</p>

CC BY-SA 3.0
2014-06-18T18:54:54.477Z
It is very unclear what you mean, but maybe you are looking for this: http://en.wikipedia.org/wiki/Newton's_identities
Sasho Nikolov
CC BY-SA 3.0
2014-06-18T19:38:04.177Z
@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
CC BY-SA 3.0
2014-06-18T21:24:10.293Z
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.
CC BY-SA 3.0
2014-06-21T20:26:20.173Z
Sum of all nonempty subset products? Dynamic programming. SubSum(N) = $s_{n}$ * SubSum(N-1) + SubSum(N-1) + $s_{n}$
Chad Brewbaker
CC BY-SA 3.0
2014-06-21T20:28:12.063Z
One question. Is $k$ fixed or does $k$ go from 1...n?
Chad Brewbaker
<ds.algorithms><co.combinatorics>
Sum of products of all combinations?
Alexander Galkin
# Sum of products of all combinations?

(Asked by: username_0 on 2014-06-18)

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?

**Tags:** ds.algorithms, co.combinatorics
> **Comments:**
> **username_1**: It is very unclear what you mean, but maybe you are looking for this: http://en.wikipedia.org/wiki/Newton's_identities  
> **username_0**: @Kaveh: I tried to edit the wording to clarify what I am looking for. This should be something rather basic math, I am sure.  
> **username_2**: 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.  
> **username_3**: Sum of all nonempty subset products? Dynamic programming. SubSum(N) = $s_{n}$ * SubSum(N-1) + SubSum(N-1) + $s_{n}$  
> **username_3**: One question. Is $k$ fixed or does $k$ go from 1...n?  

---

## 2 answers

### Answer by username_6 on 2014-06-18. Score: 11 | Accepted answer

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.


---

### Answer by username_4 on 2014-06-18. Score: 8

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

> **Comments:**
> **username_5**: 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."  

---

