1
$\begingroup$

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

$\endgroup$
0
0
$\begingroup$

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?

$\endgroup$
8
  • $\begingroup$ the way I came up with that answer was because I thought of it in this way: $\endgroup$
    – Emad
    Oct 23 '19 at 20:22
  • $\begingroup$ then... do you see the generalization to $3$ subsets? $\endgroup$
    – antkam
    Oct 23 '19 at 20:23
  • $\begingroup$ $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) $\endgroup$
    – Emad
    Oct 23 '19 at 20:24
  • $\begingroup$ 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? $\endgroup$
    – antkam
    Oct 23 '19 at 20:27
  • $\begingroup$ 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$ ? $\endgroup$
    – Emad
    Oct 23 '19 at 20:29
0
$\begingroup$

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

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.