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