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 : combinatorics


Answers 1


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

saulspatz
saulspatz
September 11, 2019 17:16 PM

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