# Counting the ordered pairs $(A, B)$, where $A$ and $B$ are subsets of $S$ and $A$ is a proper subset of $B$:

Let $S$ be a set of $n$ consecutive natural numbers. How to find the number of ordered pairs $(A, B)$, where $A$ and $B$ are subsets of $S$ and $A$ is a proper subset of $B$.

The answer in my book $3^n - 2^n$, why is this true?

-
Your book's answer makes no sense. Suppose $n=1$, for example. Well, then the only possibility is $A=\emptyset$, $B=S$. –  Cameron Buie Jun 26 '12 at 3:59
The answer is correct only when the number of elements in the set $S$ is $8$. –  user17762 Jun 26 '12 at 4:00
I have edited it. –  J.K Jun 26 '12 at 4:10

Suppose the number of proper subsets of a set with $k$ elements is $PS(k)$. Then, once you fix a subset $B$ of $S$, the number of ordered pairs that have $B$ in the second coordinate will be $PS(|B|)$. So you just need to:

1. Find what $PS(k)$ is in terms of $k$; and
2. Find out how many subsets of size $k$ there are in a set of size $n$.

Neither of these seems too hard... Can you figure them out?

-

Each element $k \in S$ occurs a total 0, 1 or 2 times in both $A$ and $B$. Furthermore, since $A \subseteq B$, if $k$ occurs exactly once, then it must be that $k \in B$ and $k \notin A$. Thus, the sets $A$ and $B$ are uniquely determined by the counts of each element. There are $3^n$ possible counts, and therefore $3^n$ ordered pairs $(A,B)$ where $A \subseteq B \subseteq S$. From this we subtract the $2^n$ pairs of the form $(A,A)$.

-
+1, very nice!$\text{}$ –  Zev Chonoles Jun 26 '12 at 4:22
Likewise! ${}{}$ –  Cameron Buie Jun 26 '12 at 4:43

First choose a $k$ element subset $B$ of $S$. This can be done in $\dbinom{n}k$ ways.

Given the subset $B$, $A$ has $2^k-1$ options (since the number of proper subset of a $k$-element set is $2^k-1$).

Hence, the total number of order pairs of sets $(A,B)$ such that $A \subset B \subseteq S$ is given by $$\sum_{k=0}^{n} (2^k-1) \dbinom{n}k = \sum_{k=0}^{n} \dbinom{n}k 2^k - \sum_{k=0}^{n} \dbinom{n}k = 3^n - 2^n$$

-

Note that $B$ cannot be empty. The number of proper subsets $A$ of a non-empty finite set $B$ is $2^{|B|}-1$, and the number of non-empty subsets of $S$ having size $0<k\leq n$ is $\binom{n}{k}$. Hence, the number is

$\begin{eqnarray*} \sum_{k=1}^n\left[\binom{n}{k}\cdot(2^k-1)\right] & = & \sum_{k=0}^n\left[\binom{n}{k}\cdot(2^k-1)\right]\\ & = & \sum_{k=0}^n\binom{n}{k}\cdot2^k - \sum_{k=0}^n\binom{n}{k}\\ & = & 3^n-2^n. \end{eqnarray*}$

To see that the sums in the second to last line yield the terms in the last line, one can use fairly simple inductive arguments.

Side note: The hypothesis that $S$ is a set of $n$ consecutive natural numbers was never used! This actually holds for any set $S$ with $n$ (distinct) elements.

-

Every non-empty subset $B$ of $S$ has at least one proper subset $A$, namely the empty set $A=\varnothing$; however the empty set has no proper subsets. Thus, the possible $B$'s we can choose are precisely the non-empty subsets of $S$.

The set $S$ has $n$ elements, so there are $\binom{n}{k}$ subsets of $S$ that have $k$ elements.

Given a non-empty subset $B\subseteq S$ with $k$ elements, there are $2^k$ subsets $A\subseteq B$, and therefore $2^k-1$ proper subsets $A\subsetneq B$.

Thus, the number of pairs $(A,B)$ where $B\subseteq S$ and $A\subsetneq B$ is $$\sum_{k=1}^n\binom{n}{k}(2^k-1)=\left(\sum_{k=1}^n\binom{n}{k}2^k\right)-\left(\sum_{k=1}^n\binom{n}{k}\right)=((1+2)^n-1)-((1+1)^n-1)=3^n-2^n$$

-