Total number of subsets of size atmost $k$ 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?
 A: 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..     
