# 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.

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

Number of subsets -> $2^n$ --> here $2^8$ number of proper subsets -> $(2^n)-1$

then how the answer is $3^n-2^n$ ?

-
Wow, I have a deja vu. I feel like this exact question was posted a year or two ago. – Asaf Karagila Jun 26 '13 at 6:00

Consider the complement.

Hint: There are $2^n$ pairs of subsets where $A = B$, which is a subset of $S$.

This follows from the rule of product, because there are 2 possibilities for each element.

Hint: There are $3^n$ pairs of subsets where $A$ is a subset of $B$, which is a subset of $S$.

This follows from the rule of product, because there are 3 possibilities for each element.

-

Let $X$, $Y$, and $Z$ be pairwise disjoint subsets of $S$ whose union is $S$. Set $A=X$, $B=X\cup Y$. Then the pair $(A,B)$ has the right property, except that if $B=A$ then $A$ is not a proper subset of $B$.

Conversely, any pair $(A,B)$ such that $A$ is a subset of $B$ uniquely determines a partition of $S$ into pairwise disjoint subsets $X$, $Y$, and $Z$ by the rule $X=A$, $Y=B\setminus A$, and $Z$ equal to the rest.

We first count the number of ways to partition $S$ into three pairwise disjoint subsets. This is just the number of functions from $S$ to the set $\{1,2,3\}$. So there are $3^n$ ways to do the partioning

Now we throw away the number of "bad" partitions where $Y=\emptyset$. This is just the number of ways to divide $S$ into $2$ sets. There are $2^n$ ways to do that.

-

When you find sets $A$ and $B$ such that $A\subsetneqq B\subseteq S$, you’re really dividing $S$ into three parts: things that are in $A$ (and of course also in $B$), things that are in $B$ but not $A$, and things that are not in $B$. In other words, evern element of $S$ belongs to exactly one of the sets $A$, $B\setminus A$, and $S\setminus B$. Conversely, if you divide $S$ into parts $X,Y$, and $Z$, you can let $A=X$ and $B=X\cup Y$ to get a pair of subsets $A$ and $B$ of $S$ such that $A\subseteq B$.

There’s nothing in the statement of the problem that prevents $A$ from being empty, so there’s no harm in letting $X=\varnothing$. There’s nothing that prevents $B$ from being all of $S$, so there’s no harm in letting $Z=\varnothing$. But we’re told that $A\subsetneqq B$, so $B\setminus A\ne\varnothing$. Thus, we must ensure that the part $Y$ of our $3$-way split of $S$ gets at least one member.

In order to build such a division of $S$ into $3$ parts, you can go through $S$ one element at a time, assigning each element in turn to $X$, $Y$, or $Z$. That’s a sequence of $n$ $3$-way choices, so by the multiplication principle it can be made in $3^n$ different ways. That is, there are $3^n$ ways to divide up $S$ into the $3$ parts $X$, $Y$, and $Z$, from which, as noted above, we get $A$ and $B$ by setting $A=X$ and $B=X\cup Y$.

However, that calculation failed to take into account the requirement that $Y$ be non-empty. How many of these unwanted divisions are there? They are essentially just divisions of $S$ into two parts, $X$ and $Z$, and the same reasoning that we used in the previous paragraph shows that there must be $2^n$ of them. Subtracting them, we find that there are $3^n-2^n$ divisions of $S$ into $3$ parts $X,Y$, and $Z$ with $Y\ne\varnothing$, so that when we set $A=X$ and $B=X\cup Y$, $A$ really is a proper subset of $B$.

-