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.$
So, for the given question, answer will be $3^{10} = 59049$
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 ${}^nC_1$ 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 ${}^nC_1 \times 2^{n-1}$
When $|A| = 2$, there are ${}^nC_2$ 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 ${}^nC_2 \times 2^{n-2}$
and so on,
When $|A| = n$, there are ${}^nC_n = 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 ${}^nC_n \times 2^0$
We want total possible pairs $(A,B)$ so we can add all the above cases :
${}^nC_0 \times 2^n + {}^nC_1 \times 2^{n-1} + {}^nC_2 \times 2^{n-2} + \dots {}^nC_n \times 2^0$
This is binomial expansion of $(1+2)^n = 3^n$
So, for the given question, answer will be $3^{10} = 59049$