# In how many ways can we choose 3 subsets, $A$, $B$ and $C$ From set $S$ with $n$ elements so that the union is $S$.

I'm having a little trouble with this combinatorics problem even though I think I've kinda figured it out.The question asks for the number of ways to choose three subsets from set $$S = \{ 1,2,3,\dots,n\}$$ so that their union is $$S$$. the thing is I already figured out the number of ways to do this for choosing two subsets which is : $$\underbrace{{n\choose n} 3 ^n}_{\text{# of unions that are equal to S}} + {n\choose n-1}3^{n-1} + {n \choose n - 2}3^{n-2} + \dots + \underbrace{{n\choose n-n} 3 ^{n-n}}_{\text{# of unions that are }\emptyset} = 4^n$$

so for choosing 2 subsets of $$S$$ it would have $$3^n$$ ways so that the union would be $$S$$. but I'm trying to find out how many ways there is with 3 subsets(also it is not mentioned that they must be disjoint). And I would also much appreciate a more general way.(maybe for $$k$$ number of subsets).

HINT

The key is to understand the $$2$$-subset case, which you solved correctly and which had a very suggestive answer. Why is the answer $$3^n$$? It is because each element $$x$$ can be in one of three colors, uh I mean, one of three situations. :) Viz, $$x \in A$$ only, or, $$x \in B$$ only, or, $$x \in A \cap B$$. After all, if the union $$A\cup B = S$$ then the only rule is that no element can be in neither $$A$$ nor $$B$$.

Now can you generalize it to $$3$$ subsets, and indeed $$k$$ subsets?

• the way I came up with that answer was because I thought of it in this way:
Oct 23 '19 at 20:22
• then... do you see the generalization to $3$ subsets? Oct 23 '19 at 20:23
• $n \choose n$ + ... + $n \choose n-n$ is the number of ways we can construct a subset of S and then I figured that there would be $3^n$ ways of getting the same union if we had two subsets.(by induction)
• hmm, forget the binomial coefficients. i'm saying $3^n$ is the answer for $2$-subsets based on a direct coloring argument: each element has choice of $3$ colors, and each choice can be independent of all others. so for $3$-subsets, how many choices can each element have? Oct 23 '19 at 20:27
• I guess that would be $7^n$ which is $x \in A$ only ,$x \in B$ only, $x \in C$ only, $x \in {A\cap C}$, $x \in {A\cap B}$, $x \in {B\cap C}$, $x \in {A\cap B\cap C}$ which is $7^n$ ?
For $$k$$ subsets to have union $$S$$
There are $$2^k$$ possible combinations of $$k$$ objects since each can either be included or not.
Each element has to be in at least one of the $$k$$ subsets and so we only need consider $$2^k-1$$ of the possibilities.
This applies to each of the $$n$$ elements of $$S$$ and so the required number of choices is $$(2^k-1)^n$$.