4
$\begingroup$

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!

  • 0
    It depends upon what you mean by closed. My formula lets you do the calculation in $O(n)$ instead of $O(n^2)$2011-11-14

2 Answers 2

1

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

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

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

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

  • 0
    Yes, the complexity savings is significant. Given that your exapansion2011-11-15
0

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.