3
$\begingroup$

What I've been thinking is that there are $2^n$ ways of choosing $A$, then from the remaining elements of $\{1,...,n\}$ I could choose any subset (there would be $2^{n-|A|}$ ways to do that) and add that to A and form B, using this same procedure we can then construct C. The total ways to choose the three subsets would be: $$ \sum_{k=0}^{n}\sum_{j=k}^{n} 2^{n}2^{n-k}2^{n-j}$$

I've tried this formula for the case n=1 and it does not work but I don't know where I went wrong.

$\endgroup$
11
$\begingroup$

We need to divide our set into $4$ pairwise disjoint parts, $A_1,A_2,A_3,A_4$ and set $A=A_1$, $B=A_1\cup A_2$, $C=A_1\cup A_2\cup A_3$, and $\{1,2,\dots,n\}=A_1\cup A_2\cup A_3\cup A_4$.

For every element $j$ of $\{1,2,\dots, n\}$, there are $4$ possible decisions: $j$ lands in $A_1$ or $A_2$ or $A_3$ or $A_4$. Thus the number of choices is $4^n$.

Remark: The number of choices for $B$ depends on the size of the set $A$. So an approach like yours should involve binomial coefficients. It can be pushed through. Ultimately you will end up calculating the sum of all the multinomial coefficients $\binom{n}{k_1,k_2,k_3,k_4}$. By the Multinomial Theorem this sum is $4^n$.

$\endgroup$
3
$\begingroup$

André Nicolas’s answer gives the easiest approach.

It’s possible to carry out the kind of analysis that you were trying, but it’s a bit messy. Let’s look first at a simpler problem: we’ll just choose $A$ and $B$. As you say, there are $2^n$ ways to choose $A$, and once $A$ is chosen, there are $2^{n-|A|}$ ways to choose the rest of $B$. However, this does not mean that there are $\sum_{k=0}^n2^k2^{n-k}$ ways to choose $A$ and $B$ so that $A\subseteq B\subseteq\{1,\ldots,n\}$. For each $k$ there are $\binom{n}k$ ways to choose $A$, and then there are $2^{n-k}$ ways to choose the rest of $B$, so by the binomial theorem there are actually

$$\sum_{k=0}^n\binom{n}k2^{n-k}=\sum_{k=0}^n\binom{n}k1^k2^{n-k}=(1+2)^n=3^n$$

to choose $A$ and $B$ so that $A\subseteq B\subseteq\{1,\ldots,n\}$.

To take $C$ into account, we again let $k=|A|$, so that $k$ runs from $0$ through $n$. We let $\ell=|B\setminus A|$; this runs from $0$ through $n-k$. For each $k$ there are $\binom{n}k$ ways to choose $A$ so that $|A|=k$, and then for each value of $\ell$ there are $\binom{n-k}\ell$ ways to choose $B\setminus A$ so that $|B|=k+\ell$. Then we can choose any subset of the remaining $n-k-\ell$ elements of $\{1,\ldots,n\}$ for $C\setminus B$. The total number of possibilities is therefore

$$\begin{align*} \sum_{k=0}^n\sum_{\ell=0}^{n-k}\binom{n}k\binom{n-k}\ell2^{n-k-\ell}&=\sum_{k=0}^n\binom{n}k\sum_{\ell=0}^{n-k}\binom{n-k}\ell2^{(n-k)-\ell}\\ &=\sum_{k=0}^n\binom{n}k3^{n-k}\\ &=\sum_{k=0}^n\binom{n}k1^k3^{n-k}\\ &=4^n\;. \end{align*}$$

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