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).
Best Answer
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$.