0

Given $|X|=n$, how many $(A,B,C,D)$ exist if $C \cap B=C \cap D= B\cap D =\varnothing$, $A \subset B$, $B \cup C \cup D =X$?

Mary Star
  • 13,956

1 Answers1

0

It seems useful to note $k$ the cardinal of $B$. Given $0\leq k\leq n$, there are $n \choose k$ such sets $B$. Moreover, for each of these $B$, there are $2^k$ possible sets $A\subset B$. All these $2^k{n \choose k}$ combinations yields different couples $(A,B)$.

Then, we know from the hypotheses that $\{B,C,D\}$ is a partition of $X$, so that $D$ is determined by the choice of $B$ and $C$. Given $A$ and $B$, choosing $C$ is equivalent to choose a subset of $X-B$. There are $2^{n-k}$ such subsets.

Therefore, the final answer is

$$\sum_{k=0}^n 2^k{n \choose k}2^{n-k}=2^n\sum_{k=0}^n {n \choose k}=2^{2n}.$$

TerranDrop
  • 840