Suppose that you have a multiset of positive integers $I$.

$I$ is not given, but it is known that the sum over all elements of $I$ = $k$.

(e.g. if $I$={2,5,7} then k=14 is given, but I is unknown).

We are also given another integer $r$.

$S\subseteq I$ will be called $r-minimal-subset$, if $sum(S)>r$,

and for every $x\in S$, $sum(S$\{x}$) \leq r$.

For example, if $I$={1,3,3,5,7,8} and r=10,

then {3,3,5} and {1,3,7} are r-minimal-subset, but {5,7,8} is not (as the subset {7,8} 's sum is 15. {7,8} is a r-minimal-subset).

What is the the best upper bound we can give on the number of $r-minimal-subsets$ of I?

(In this setting, we get is $(r,k)$, while $I$ is being chosen by an adversary).


Edit: Hmm, sorry for the question.

Obviously the answer is $k \choose r+1$, for I={1,1,..,1}, $|I|=k$. It doesn't let me answer the question, so you could go ahead :/.


1 Answer 1


Let me know if I understood the question correctly: you want to count the sets of $n$ positive integers summing exactly $k$, right? This is $\binom{n+k+1}{k}$. If you want for non-negative integers version, add one more number to the count, $\binom{n+k+1}{k+1}$.

  • 1
    $\begingroup$ No, that's not what s/he's trying to compute. $\endgroup$ Commented Dec 30, 2013 at 17:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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