I was working on a problem that involved taking subsets of a multiset. I want to count the total number of distinct subsets of size at most $ k$.

Example 1:

consider the multiset $S = \{ 3, 3, 5, 7 \}$ and $k=3$ then the answer should be $12 $.

That is $\{ \}, \{ 3 \}, \{ 3 \}, \{ 5 \}, \{ 7 \}, \{ 3, 5 \}, \{ 3, 7 \}, \{ 3, 5 \}, \{ 3, 7 \}, \{ 5, 7 \}, \{ 3, 5, 7\}, \{ 3, 5, 7 \} = 12$ subsets.

Example 2:

$S = \{ 2, 3, 5 \}$ and $k=2$ then the answer should be $7.$

$\{ \}, \{ 2 \}, \{ 3 \}, \{ 5 \}, \{ 2, 3 \}, \{ 2, 5 \}, \{ 3, 5 \} = 7$ subsets

By using the formula from this answer I can count the total number of distinct subsets. How can I extend that formula for my constraints? Any idea?

  • $\begingroup$ For some basic information about writing mathematics at this site see, e.g., basic help on mathjax notation, mathjax tutorial and quick reference, main meta site math tutorial and equation editing how-to. $\endgroup$ – Thomas Shelby Sep 11 at 17:04
  • $\begingroup$ sorry for that.please edit my question if i make any mistake. $\endgroup$ – Midhun Manohar Sep 11 at 17:07
  • $\begingroup$ I do not follow your first example. Why do include $\{3\}$ twice? Why do you include $\{3,5\}$ twice? Why also did you not include $\{3,3\},\{3,3,5\}$ or $\{3,3,7\}$? If you intend for each $3$ to be considered distinct... then why do you use identical characters for them? It would have made more sense to never consider multisets in the first place and instead talk about the subsets of size at most $3$ from the set $\{3,\color{red}{X},5,7\}$ instead where we replaced the second three with $X$... at which point you have $\sum\limits_{i=0}^k\binom{n}{k}$ such subsets. $\endgroup$ – JMoravitz Sep 11 at 18:33
  • $\begingroup$ elements of the subset should be distinct $\endgroup$ – Midhun Manohar Sep 12 at 5:04

Let me restate the problem, and see if you agree that it is the same thing. We have a finite collection of elements of types $1,2,\dots,n$ with $a_j$ elements of type $j$ for $j=1,2,\dots,n$, and we wish to know how many ways we can select at most $k$ objects, subject to the condition that no more than one element of any type is selected.

In your first example, we have $2$ elements of type "$3$" and one element of each of types "$5$" and "$7$".

Exactly $k$ elements may be selected in $$\sum a_{j_1}a_{j_2}\cdots a_{j_k}$$ ways, where the sum is over all $k$-tuples $(j_1,j_2,...j_k)$ with $1\leq j_1<j_2<\cdots<j_k\leq n$

If you want at most $k$ objects, just add up the values for each nonnegative integer $\leq k$.

In you first example, with $n=3$, we have $a_1=2,a_2=1,a_3=1$. When $k=0$ we have an empty product, so the value is $1$. When $k=1$, we get $2+1+1=4.$ When $k=2$, we get $2\cdot1+2\cdot1+1\cdot1=5$. When $k=3$, we get $2\cdot\cdot1=2$. Altogether, we have $1+4+5+2=12.$

I gave a more concrete answer to a similar question a few days ago. Look at Find number of ways to select subset with distinct objects of at most K size..

  • $\begingroup$ it seems working.can you elaborate more $\endgroup$ – Midhun Manohar Sep 11 at 17:30
  • $\begingroup$ @Midhunmanohar What is it that you don't understand? $\endgroup$ – saulspatz Sep 11 at 17:32
  • $\begingroup$ i have never seen use of multiplier symbol ∏ like this.can you please elaborate the formula more $\endgroup$ – Midhun Manohar Sep 12 at 6:06
  • $\begingroup$ @Midhunmanohar That was my fault. I meant sum, not product. No wonder you didn't understand. I don't know where my mind was. Anyway, it's the sum over all such products. I've edited my answer with a link to another answer that may be easier to follow. $\endgroup$ – saulspatz Sep 12 at 10:47

Your Answer

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

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