# Counting pairs of subsets

Let A be a finite set. Show that there are $3^n - 2^n$ tuples (X,Y) where $X \subset Y \subseteq A$ and $n = \#A$.

I tried to count the possibilities to build such tuples. There are $\sum_{k=1}^n \binom{n}{k}$ ways to build such a Y. Because of the condition $X \subset Y$ the corresponding $X$ may only contain less elements than $Y$. This leads me to $$\sum_{k=1}^n \binom{n}{k} \cdot \sum_{i=0}^{k-1} \binom{k}{i}$$ Even though this formula seems to be correct, I still don't bring it together with $3^n - 2^n$. Can you please help me to go on with this proof?

-

Hint:

• To count tuples $(X,Y)$ with $X \subseteq Y \subseteq A$, observe that each element $a \in A$ has three options:

• $a \in X \land a \in Y$,
• $a \notin X \land a \in Y$,
• $a \notin X, a \notin Y$.

Observe that $a \in X \land a \notin Y$ is not an option because of $X \subseteq Y$.

Therefore, there are $3^n$ such pairs of sets.

• To count tuples $(X,Y)$ with $X = Y \subseteq A$, each element has two options $a \in X = Y$ and $a \notin X = Y$, hence, $2^n$ such tuples.

• The smaller of the two above sets is contained in the other and $$\Big\{(X,Y) \ \Big|\ X \subsetneq Y \subseteq A \Big\} = \Big\{(X,Y) \ \Big|\ X \subseteq Y \subseteq A \Big\} \setminus \Big\{(X,Y) \ \Big|\ X = Y \subseteq A \Big\}.$$

I hope this helps $\ddot\smile$

-
great, thank you! – muffel Apr 19 '14 at 15:13

For your sum, note that: $$\sum_{0 \le r \le s} \binom{s}{r} = 2^s$$ so that: \begin{align} \sum_{1 \le k \le n} \binom{n}{k} \sum_{0 \le i \le k - 1} \binom{k}{i} &= \sum_{1 \le k \le n} \binom{n}{k} (2^k - 1) \\ &= \sum_{1 \le k \le n} \binom{n}{k} 2^k - \sum_{1 \le k \le n} \binom{n}{k} \\ &= ((2 + 1)^n - 1) - (2^n - 1) \\ &= 3^n - 2^n \end{align}

-