<p>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}$.</p>

CC BY-SA 3.0
2013-12-30T17:31:44.130Z
No, that's not what s/he's trying to compute.
David Richerby
CC BY-SA 3.0
2013-12-30T14:47:51.610Z
2013-12-30T14:47:51.610Z
Cássio
<p>Suppose that you have a multiset of positive integers $I$.</p>

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

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

<p>We are also given another integer $r$.</p>

<p>$S\subseteq I$ will be called $r-minimal-subset$, if $sum(S)&gt;r$,</p>

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

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

<p>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).</p>

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

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

<p>~~~~~~~~~~~~~~~~~~~~~~~~~~</p>

<p>Edit:
Hmm, sorry for the question.</p>

<p>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 :/.</p>

<co.combinatorics><upper-bounds>
Counting subsets with large sum
Ran B
# Counting subsets with large sum

(Asked by: username_0 on 2013-12-30)

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

**Tags:** co.combinatorics, upper-bounds

---

## 1 answers

### Answer by username_1 on 2013-12-30. Score: -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}$.

> **Comments:**
> **username_2**: No, that's not what s/he's trying to compute.  

---

