0
$\begingroup$

Suppose we are given an integer $n$ and an integer $i$ where $i \le n$. We want to find all the subsets of {1, 2, 3 ... n-1} of size $i$ that will sum to $kn$ where $k$ is a positive integer.

Edit: I do realize this resembles the stars and bars question that has been asked many times here. This is however asking for distinct values so if $n=5$ and $i=3$, $(3,1,1)$ is not a solution.

So far, I've tried an enumeration approach and I've worked out the answer to be extracting the coefficient from a function like so:

$$[y^i][x^{kn}]\prod \limits_{j = 1}^{n-1} (1 + yx^j)$$

The power's of x should combine distinct values for the sum and the y's will count the number of values used.

I'm not sure how to go about solving this, any ideas would be greatly appreciated!

$\endgroup$
  • $\begingroup$ Do you want to find all the subsets, or do you want to count how many there are? $\endgroup$ – Patrick Da Silva Jun 16 '13 at 14:22
  • $\begingroup$ I just want to count how many there are $\endgroup$ – Azhuang Jun 16 '13 at 14:29
  • 1
    $\begingroup$ Okay, so that product can be written as $1 + y p_1(x) + y^2 p_2(x) + \dots + y^{n-1} p_{n-1}(x)$, where the coefficient of $p_i(x)$ in front of $x^p$ is the number of subsets of size $i$ who sum up to $p$. So why don't you just look at the coefficient in front of $x^{kn}$ in that expansion? Is that what those brackets mean? Because I don't think they should be factors in that expansion. For me this problem is already solved. What exactly do you need? An explicit formula? $\endgroup$ – Patrick Da Silva Jun 16 '13 at 14:35
  • $\begingroup$ Yup, what you have written is pretty close to what I've been thinking and finding the coefficients is exactly what the brackets mean. I am looking for a a closed form solution so that I can manipulate the value obtained by the coefficients. $\endgroup$ – Azhuang Jun 16 '13 at 14:45
  • 1
    $\begingroup$ So I wish to find an explicit formula for any n and i $\endgroup$ – Azhuang Jun 16 '13 at 14:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.