Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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

2 Answers 2

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.

share|improve this answer
1  
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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.