Originally Posted by
awkward I'm going to assume that we consider
A={1}, B={1,2}
and
A={1,2}, B={1}
to be distinct cases.
How many ways are there to select two subsets without any restriction? Each element of {1, 2, ..., n} can be in
(1) neither A nor B,
(2) in A only,
(3) in B only, or
(4) in both A and B.
So there are 4^n ways to select A and B.
How many ways are there if A and B must be disjoint? We simply eliminate case (4) above. So there are 3^n ways to select A and B if they must be disjoint.
So the number of ways to select A and B if they must not be disjoint is 4^n - 3^n.