How many pairs of sets $(X,Y)$ exist such that $X \subset Y \subset [n]$?

Question

Consider $[n]=\{1,2,\dots,n\}$ an unordered set. How many pairs of sets $(X,Y)$ exist such that $X \subset Y \subset [n]$?

Answer 1

All this solves the problem of counting the number of sets $X$ and $Y$ such that $X\subseteq Y \subseteq [n]$, not with strict inequalities.

Suppose we condition on the size of set $Y$, how many subsets of $Y$ are there ? If $|Y|=k$, then there $2^k$ of those, since every element can be in $X$ or be in $X^c$, which create $2$ possibilities for all elements of $Y$. Also there are $n \choose k$ different sets $Y$ such that $|Y|=k$. Hence the answer you seek is given by \begin{align*} \sum_{k=0}^{n} {n\choose k} 2^k &= \sum_{k=0}^{n} {n\choose k} 2^k1^{n-k}\\ &= 3^n \end{align*}

By Newton's formula.

---

Seeing this result gives us the intuition that there may be a faster way to get there. Every number $i$ in $[1:n]$ have $3$ possibilities :

• $i\notin Y$

• $i\in Y$ and $i\notin X$

• $i\in X$

This creates $3$ choice for every number in $[1{:}n]$ hence the number of possibilities is $3^n$

---

If you want to have strict $X\subset Y \subset [n]$, then we need to remove from these the case where $Y=[n]$ and each cases where $X=Y$, hence the summation becomes

\begin{align*} \sum_{k=0}^{n-1} {n\choose k} (2^k-1) &= \sum_{k=0}^{n-1} {n\choose k} 2^k - \sum_{k=0}^{n-1} {n\choose k}\\ &= 3^n-2^n-(2^n-1)\\ &=3^n-2^{n+1}+1 \end{align*}