Q.20 What is the number of ordered pairs $(π΄, π΅)$ where $π΄$ and $π΅$ are subsets of $\{1,2, . . . ,5\}$ such that neither $π΄ β π΅$ nor $π΅ β π΄$?
Ans: πππ
Hint: Use principle of Inclusion-Exclusion.
Solution: Let $X$ denote the set of all ordered pairs $(A, B)$ when $A β B$. Similarly let $Y$ denote set of all ordered pairs $(A,B)$ when $B β A$. The question asks to find $$π(X'\cap Y') = π(π) β π(π\cupπ) $$$$= π(S) β π(X) β π(Y) + π(X\cap Y) $$$$= 2^{10} β 3^5 β 3^5 + 2^5 = 570$$.
How did this happen? What is $S$? If $S={1,2,3,4,5}$, shouldn't $n(S)=2^5$? And where do the $3^5$s come from? I cannot understand this.
Also, are there other ways to solve this?
Best Answer
$S$ is the set of ordered pairs $(A, B)$, where $A, B \subseteq \{1, 2, 3, 4, 5\}$.
The number of subsets of $\{1, 2, 3, 4, 5\}$ is $2^5$ since we can choose to include or not include each element in the set in a subset. Hence, there are $2^5$ ways to select set $A$ and $2^5$ ways to select $B$. Since subsets $A$ and $B$ may be selected independently, there are $2^5 \cdot 2^5 = 2^{10}$ ordered pairs of subsets $(A, B)$.
If $A \subseteq B$, then there are three possibilities for each of the five elements in the set $\{1, 2, 3, 4, 5\}$. Either it is in set $A$, set $B - A$, or neither subset. Thus, there are $3^5$ ordered pairs $(A, B)$ with $A \subseteq B$.
By symmetry, there are also $3^5$ ordered pairs $(A, B)$ in which $B \subseteq A$.
If $A \subseteq B$ and $B \subseteq A$, then $A = B$. Since each of the five elements in $\{1, 2, 3, 4, 5\}$ is either in $A$ or not in $A$, there are $2^5$ ordered pairs of subsets $(A, B)$ in which $A = B$.