3
$\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
    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$2$). Similar expressions can be found for other $k$, using the distributive law, but they become more complicated. – 2011-11-14
  • 0
    @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 ?2011-11-14
  • 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

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

  • 1
    For more of this kind of expansion, see http://en.wikipedia.org/wiki/Newton%27s_identities#Expressing_elementary_symmetric_polynomials_in_terms_of_power_sums2011-11-14
  • 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.