# Count Subsets of size less than equal to k [duplicate]

This is a variation of question asked on this site before.

Consider a set with $$𝑎_1$$ 'distinct' 1s, $$𝑎_2$$ 'distinct' 2s, ... , $$𝑎_𝑛$$ 'distinct' ns. You have $$𝑎_1+1$$ choices for the 1s (including the option of none of them being chosen) and similarly for the other elements. The total number of subsets is therefore $$(𝑎_1+1)(𝑎_2+2)...(𝑎_𝑛+1)$$

Now how to find the number of subsets with size $$\leq$$ 'k'.

We have the multiset $$\{ 1^{a_1} ,2^{a_2} , \cdots ,n^{a_n}\}$$ (where multiplicity of the elements is indicated by the expononent). The number of subsets (of size $$k$$) will be the coefficient of $$x^k$$ in the function below $$\begin{eqnarray*} (1+x+ \cdots +x^{a_1}) (1+x+ \cdots +x^{a_2}) \cdots (1+x+ \cdots +x^{a_n}). \end{eqnarray*}$$