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?
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?
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:
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)$.
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
$\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.
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$
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$