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

Question

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).

Answer 1

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

Answer 2

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?