I have a multiset $G$ containing $n$ elements and I want to count the number of subsets that has $k$ elements and the ordering within the subsets does not matter. The multiset $G$ would look as this: $\{n_0 * 0, n_1 * 1, \dots, n_r * r\}$. Where $n_i$ is the number of occurrences of element $i$ and $\sum_{i=0}^r n_i = n$.

For example, take the multiset $S = \{0,0,1,2\}$ and $k=1$. The '$|$' denotes the separation of the elements that we choose and didn't choose. The large bracket '$\large\{$' encloses the multiset permutations that reduce to the same subset of cardinality $k=1$. $$ \begin{align} \begin{cases} \{0|0,1,2\}\\ \{0|0,2,1\}\\ \{0|1,0,2\}\\ \{0|1,2,0\}\\ \{0|2,0,1\}\\ \{0|2,1,0\}\\ \end{cases}\\ \begin{cases} \{1|0,0,2\}\\ \{1|0,2,0\}\\ \{1|2,0,0\} \end{cases}\\ \begin{cases} \{2|0,0,1\}\\ \{2|0,1,0\}\\ \{2|1,0,0\} \end{cases} \end{align} $$

What would a formula to count the number of subsets of cardinality $k$ given an arbitrary $n,k$ and $n_i$'s.


Your Answer

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

Browse other questions tagged or ask your own question.