
4. Let $X=\{1,2,3, \ldots, 11\}$. Find the the number of pairs $\{A, B\}$ such that $A \subseteq X$, $B \subseteq X, A \neq B$ and $A \cap B=\{4,5,7,8,9,10\}$.


Solution: Let $A \cup B=Y, B \backslash A=M, A \backslash B=N$ and $X \backslash Y=L$. Then $X$ is the disjoint union of $M, N, L$ and $A \cap B$. Now $A \cap B=\{4,5,7,8,9,10\}$ is fixed. The remaining 5 elements $1,2,3,6,11$ can be distributed in any of the remaining sets $M$,
$N, L$. This can be done in $3^{5}$ ways. Of these if all the elements are in the set $L$, then $A=B=\{4,5,7,8,9,10\}$ and this case has to be omitted. Hence the total number of pairs $\{A, B\}$ such that $A \subseteq X, B \subseteq X, A \neq B$ and $A \cap B=\{4,5,7,8,9,10\}$ is $3^{5}-1$.
