We want the ordered pairs $(A,B)$ where $(A \subseteq S , B \subseteq S ; A \subseteq B ;)$
Let’s find general solution i.e. when $|S| = n$
Method 1 :
We want the ordered pairs $(A,B)$ where $(A \subseteq S , B \subseteq S ; A \subseteq B ;)$
For every element $x$ of set $S, $ we have three choices :
Choice 1 : $x \notin A \,\, and \,\,x \notin B$
Choice 2 : $x \notin A \,\, and \,\,x \in B$
Choice 3 : $x \in A \,\, and \,\,x \in B$
So, for each element we have 3 choices, and we have $n$ elements , so, answer will be $3^n.$
NOTE : This method is nice and can be used to solve a wide variety of problems/variations very easily and in less time.
For example, Try the following variations :
Variation 1 : Find the number of ordered triples $(A,B,C)$ where $(A,B,C \subseteq S ; A \subseteq B \subseteq C ;)$
Answer : For every element $x$ of set $S, $ we have 4 choices. So, $4^n$
Variation 2 : Find the number of ordered triples $(A,B,C)$ where $(A,B,C \subseteq S ; A \subseteq B \supseteq C ;)$
Answer : For every element $x$ of set $S, $ we have 5 choices. So, $5^n$
Variation 3 : Find the number of ordered triples $(A,B,C)$ where $(A,B,C \subseteq S ; A \subseteq B ; A \subseteq C ;)$
Answer : For every element $x$ of set $S, $ we have 5 choices. So, $5^n$
Variation 4 : Find the number of ordered triples $(A,B)$ where $(A,B \subseteq S ; A \cap B = \phi )$
Answer : For every element $x$ of set $S, $ we have 3 choices. So, $3^n$
Many more questions can be easily solved by this method, so it is good to practice it.
Method 2 :
If we make ordered pairs $(A,B)$ where $(A \subseteq S , B \subseteq S ; A \subseteq B ;)$ such that $A$ has $k$ elements in it then for $B$ we have $2^{(n-k)}$ possible choices. (Because those $k$ elemetns of $A$ must in present in $B$ so there is no choice for them But for each of the remaining $n-k$ elements of $S,$ we have 2 choices for each element)
For example, if $A = \{ a1,a2 \}$ then how many supersets are possible for $A ?$
There will be $2^{n-2}$ supersets of $A.$
So the number of ordered pairs $(A,B)$ where $(A \subseteq S , B \subseteq S ; A \subseteq B ;)$ that we have :
We can divide it into cases :
When $|A| = 0 $ OR $|A| = 1$ OR $|A| = 2$ OR $\dots $ $|A| = n$
When $|A| = 0$, there is only one such $A$ is possible, that is $A = \phi$, So, number of possible $B's = 2^n ; $ So total $(A,B)$ pairs in this case will be $1 \times 2^n$
When $|A| = 1$, there are $nC1$ such $A$ possible, So, for each possible $A$, the number of possible $B's = 2^{n-1} ; $ So total $(A,B)$ pairs in this case will be $nC1 \times 2^{n-1}$
When $|A| = 2$, there are $nC2$ such $A$ possible, So, for each possible $A$, the number of possible $B's = 2^{n-2} ; $ So total $(A,B)$ pairs in this case will be $nC2 \times 2^{n-2}$
and so on,
When $|A| = n$, there are $nCn = 1$ such $A$ possible, So, for each possible $A$, the number of possible $B's = 2^{n-n} = 2^0 ; $ So total $(A,B)$ pairs in this case will be $nCn \times 2^0$
We want total possible pairs $(A,B)$ so we can add all the above cases :
$nC0 \times 2^n$ + $nC1 \times 2^{n-1}$ + $nC2 \times 2^{n-2}$ + $\dots$ $nCn \times 2^0$
This is binomial expansion of $(1+2)^n = 3^n$