# Total number of subsets of size atmost $k$

by Midhun manohar   Last Updated September 11, 2019 17:20 PM

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?

Tags :

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 $$\prod a_{j_1}a_{j_2}\cdots a_{j_k}$$ ways, where the product is over all $$k$$-tuples $$(j_1,j_2,...j_k)$$ with $$1\leq j_1

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.$$

## Related Questions

Updated December 20, 2017 00:20 AM

Updated April 22, 2015 22:08 PM

Updated September 27, 2017 02:20 AM

Updated August 16, 2018 13:20 PM

Updated March 21, 2019 18:20 PM