Combinatorics – Number of Possible Subsets of All Sizes

combinatorics

  1. Given a set of elements $S$ of size $n,$ where some elements may be repeated, what is the total number of subsets that can be made from $S,$ including all sizes from $2$ to $n-1?$ Note: the ordering of elements does not matter.

    • $S$ could be e.g. $S=\{el_1,el_1,el_2,el_3,…,el_n\}.$ Notice some elements are repeated. For example a subset of size 3 would be $\{el_1,el_3,el_2\}.$

  2. How does the count of possible subsets change when two specific elements (e.g. $el_1,el_2,$ hence the size of subsets starting from $2$) have to be in every considered subset?

My own guess is: we know that if the order does not matter then there are $$\frac{n!}{(n-k)!k!} \tag{1}$$ ways of picking k elements from n. Thus the total number of subsets with $k$ going from $2$ to $n-1$ is given by:
$$
\sum_{k=2}^{n-1}\frac{n!}{(n-k)!k!} \tag{2}
$$
But I do not know whether formula $(1)$ holds if there are repeating elements among the $n$ elements of the initial set. If it holds, then I suspect my $(2)$ should give the correct count at least for part 1.

An example: say the set of elements are $\{a,a,b,c\}$ then all the subset of 3 elements where order doesn't matter would be: $\{a,a,b\},\{a,a,c\},\{a,b,c\}$ so only 3 possibilities whereas $(1)$ gives 4 because it assumes distinct elements in the original set.

Best Answer

Note that to find the total number of possible subsets of $n$ distinct elements, it is the same as putting the $n$ distinct elements into $2$ distinct boxes. In other words, each distinct element is either in the subset or not in the subset.

Therefore, the total number of subsets = $2^n$ (this includes the $\varnothing$ of no elements)

At the same time, the total number of subsets can also be calculated as you suggested in $(1)$ and $(2)$: $$\sum_{k=0}^{n}\frac{n!}{(n-k)!k!} = \sum_{k=0}^{n}\binom{n}{k}=2^n$$

This will allow you to find a "nicer form" for your expression in $(2)$.

$$ \binom{n}{0}+\binom{n}{1}+\binom{n}{n}+\sum_{k=2}^{n-1}\binom{n}{k}=2^n$$

$$\sum_{k=2}^{n-1}\binom{n}{k}=2^{n}-n-2$$

When there are identical terms, we will have to first count the number of subsets of the distinct terms (let us assume there are $a$ number of some identical term).

We will have $2^{(n-a)}$ subsets of distinct terms.

Now we will count the number of subsets of $a$ identical terms or find the number of ways to distribute $a$ identical terms into $2$ distinct boxes: $$\binom{a+2-1}{2-1} = a+1$$

This uses the "stars and bars" method where the distribution of $n$ identical objects into $k$ distinct boxes, empty boxes are allowed is given by:

$$\binom{n+k-1}{k-1}$$

In the above case, we had $a$ objects and $2$ distinct boxes, i.e, "in the subset" or "not in the subset".

We can then multiply the two together to find the number of subsets of the $(n-a)$ distinct terms and $a$ identical terms again including $\varnothing$. Once you get your final value, it only includes the null set once so you can choose to minus $1$ if you do not wish to count the null set.

If we have multiple sets of identical elements, for example, $S=\{el_1,el_1,el_2,el_3,...,el_n\}$ and with $a$ number of '$el_a$'s, $b$ number of '$el_b$'s and so on.

The total number of subsets is then given by:

$$2^{(n-a-b-\dots)} (a+1)(b+1)(c+1)\dots$$

Related Question