[Math] 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$.

elementary-set-theory

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

Best Answer

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.