Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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
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|cite|improve this answer

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|cite|improve this answer
+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$$

share|cite|improve this answer

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|cite|improve this answer

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|cite|improve this answer

Your Answer


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.