1
$\begingroup$
  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.

$\endgroup$
  • $\begingroup$ The answer obviously depends on how many elements are repeated and how many times, so you should treat these as parameters of your problem. $\endgroup$ – uniquesolution Oct 23 '15 at 13:34
  • $\begingroup$ It seems to me that in 1) you are asking for $\sum_{k=2}^{n-1}\left|\mathcal{F}_{k}\right|$ where $\mathcal{F}_{k}:=\left\{ f\in\omega^{\left\{ 1,\dots,n\right\} }\mid\sum_{i=1}^{n}f\left(i\right)=k\right\} $ and $\omega$ denotes the set of nonnegative integers. Is that correct? $\endgroup$ – drhab Oct 23 '15 at 14:34
  • $\begingroup$ @drhab The elements of the set could also be letters, I didn't specify them to be integers necessarily. I added an edit to clarify some things. $\endgroup$ – user186225 Oct 23 '15 at 14:45
  • $\begingroup$ What is the size of $\{el_1,el_1,el_3,el_2\}$? Is it $3$ or is it $4$? $\endgroup$ – drhab Oct 23 '15 at 14:59
  • $\begingroup$ @drhab 4, we count all, repeated ones included, as they are allowed. (in other words, I'm not talking of the size of the corresponding mathematical set) $\endgroup$ – user186225 Oct 23 '15 at 15:01
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ You're welcome. a) we must count subsets of the distinct and the repeated terms separately. Let me give an example. Consider the set $(1,3,3)$. The possible subsets are $\varnothing,(1),(3),(1,3),(3,3),(1,3,3)$. Subset of only distinct numbers is $\varnothing,(1)$. Subset of identical numbers are $\varnothing,(3),(3,3)$. This means that to each of the subset of distinct numbers we can put in either no $3$ one $3$ or two $3$s. I will answer b) and c) in edit. $\endgroup$ – Nicholas Oct 24 '15 at 15:55

Your Answer

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