Number of ordered pairs of subsets

Question

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?

Answer 1

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

Answer 2

There are $\binom{5}{n}$ subsets of $\{1,2,3,4,5\}$ that contain $n$ elements. The number of subsets of an $n$-element set is $2^n$. So the number of subsets A such that $A \subseteq B$ is

$$\binom n0 2^0 + \binom n1 2^1 + \binom n2 2^2 + \cdots + \binom n5 2^5 = (1+2)^5 = 3^5$$

So $n(X) = n(Y) = 3^5$.

Answer 3

$S$ is the set of all ordered pairs. You have $2^5$ ways to choose $A$ as a subset of $\{1,2,3,4,5\}$, similarly for $B$. Hence, $n(S)=2^5\times 2^5=2^{10}$. Now, let's consider the set $X$. Let $(A,B)\in X\Leftrightarrow A\subseteq B$. Let $k$ be the cardinality of $A (0\leq k\leq 5$). There are $\left(\begin{matrix}5 \\ k\end{matrix}\right)$ choices of such $k$-subsets. Now, you already have $A$ and you need to count the number of ways to choose $B$ such that $A\subseteq B$. This means that you need count the number of ways to add 0 to 5-k elements which is not in $A$ to $A$. Hence, the number of such $B$ is the number of subsets of a set of $5-k$ elements. Therefore, the number of such $B$ is $2^{5-k}$. Thus, $n(X)=\sum_{0\leq k\leq 5} \left(\begin{matrix}5 \\ k\end{matrix}\right)2^{5-k}=3^5$. Similarly for $n(Y)$. $n(X\cap Y)$ is trivial.