4. Let X = {1, 2, 3, … , 10}. Find the number of pairs {A, B} such that A ⊆ X, B ⊆ X, A ≠ B and A∩B = {5, 7, 8}.
Solution:
First we put 5, 7, 8 in each of A and B.
We are left out with 7 elements of X.
For each of these 7 elements there are three choices:
a) it goes to A
b) it goes to B
c) it goes to neither A nor B
Hence there are total (3^7) = 2187 choices. From these 2187 cases we delete that one case where all of the seven elements goes to neither A nor B as A≠ B thus giving 2187 -1 = 2186 cases.
Since A and B is unordered (that is A= {5, 7, 8, 1, 2} , B = {5, 7, 8, 4} is the same as B= {5, 7, 8, 1, 2} , A = {5, 7, 8, 4} ) we take half of these 2186 cases that is 1093 cases.
Hence there are 1093 such pairs.