# How many ways are there to choose three subsets $A, B$ and $C$ of $\{1,…,n\}$ such that $A \subseteq B \subseteq C$?

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.

## 2 Answers

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

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*}