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$ ?
Please explain..
 A: 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.
A: 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$.
A: 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. 
A: Fix the the cardinality of $B$, and find how many sets $A$ are there such that $A\subset B$? The answer is $\mathcal{P}(B)-1$.
Now we just need to sum over all subsets of $S$, $$N=\sum_{B\subseteq S}\left(\mathcal P(B)-1\right)=-2^n+\sum_{B\subseteq S}\mathcal P(B)$$
Since $\mathcal P(B)=2^{|B|}$ we get $$N=-2^n+\sum_{B\subseteq S} 2^{|B|}=-2^n+\sum_{k=1}^n\sum_{|B|=k}2^{|B|} $$
The question ''How many subsets of $S$ are there with caridinality $k$'' rise up here. And the answer is $n$ choose $k$. Hence $$N=-2^n+\sum_{k=1}^n{n \choose k}2^k=3^n-2^n$$
Because $$3^n=(1+2)^n=\sum_{k=1}^n{n \choose k}2^k$$
Which follows form the binomial theorem.
