# Sum of products of $k$-sets taken from a ground set of $n$ elements

Given a set $S$ with $n$ elements, and an integer $k$. I need to find the sum of products of all $\binom{n}{k}$ subsets of $S$ of size $k$. That is, if $S = \{1,2,3,4\}$ and $k = 2$, then I am looking for $P = 1\cdot 2 + 1 \cdot 3 + 1 \cdot 4 + 2 \cdot 3 + 2 \cdot 4 +3 \cdot 4$. Note that product-pairs constitute the set -- taking $k$ distinct elements from a set of $n$ elements. I can formulate a simple dynamic programming version of this:

$$P(n,k) = a_{n}P(n-1,k-1) + P(n-1,k) .$$

That is, take $n-1$ elements and choose $k-1$ and add $a_{n}$ as well as leave out $a_n$. Is there some nice theory to find a closed form solution to the above problem? I am a bit lacking on advanced maths, though programming excites me. I was able to derive the aforementioned DP but could not proceed to a closed form which I hope there is!

-
For $k=2$ you can use the fact that $\left(\sum_n a_n\right)^2=\left(\sum_n a_n^2\right)+2\sum_{i<j}a_ia_j$. Your expression is the third term (without the factor $2$). Similar expressions can be found for other $k$, using the distributive law, but they become more complicated. – Ross Millikan Nov 14 '11 at 18:27
@RossMillikan: Thanks for your response. I should have stated that for $k=2$ your equation indeed serves the purpose. It's when we increase $k$ that problem arrives. Also in that case will the formulation be closed ? – Sanket Nov 14 '11 at 18:32
It depends upon what you mean by closed. My formula lets you do the calculation in $O(n)$ instead of $O(n^2)$ – Ross Millikan Nov 14 '11 at 18:42

For $k=2$ you can use the fact that $\left(\sum_n a_n\right)^2=\left(\sum_n a_n^2\right)+2\sum_{i<j}a_ia_j$. Your expression is the third term (without the factor $2$). For $k=3,$

$\left(\sum_n a_n\right)^3=\left(\sum_n a_n^3\right)+3\sum_{i\ne j}a_i^2a_j+6\sum_{i<j<k}a_ia_ja_k$

$=\left(\sum_n a_n^3\right)+3\sum_i a_i^2((\sum_ja_j)-a_i)+6\sum_{i<j<k}a_ia_ja_k$

$=3(\sum_i a_i^2)(\sum_ja_j)-2\left(\sum_n a_n^3\right)+6\sum_{i<j<k}a_ia_ja_k$

and again you are at $O(n)$. I suspect these are available somewhere, because they get messy.

-
For more of this kind of expansion, see en.wikipedia.org/wiki/… – Byron Schmuland Nov 14 '11 at 20:02
Yes, the complexity savings is significant. Given that your exapansion – Sanket Nov 15 '11 at 17:51

The generating function for this is $B_n(x) = \sum P(n,k)x^k = (1+x)(1+2x)\ldots (1+nx)$. You might be able to manipulate this to get a closed form. For example, $\log(B_n(x)) = \sum(-1)^kS_kx^k/k$ where $S_k$ is the sum of $k_{th}$ powers. Still, no closed formula.

-