Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
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
1  
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
add comment

5 Answers

up vote 4 down vote accepted

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?

share|improve this answer
add comment

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

share|improve this answer
1  
+1, very nice!$\text{}$ –  Zev Chonoles Jun 26 '12 at 4:22
1  
Likewise! ${}{}$ –  Cameron Buie Jun 26 '12 at 4:43
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.