Thread: Subsets

We want to select two subsets A and B of [n] so that . In how many different ways can we do this?

First we find how many ways are there to choose two subsets and of without worrying about what their intersection is.

There are ways of doing this.
Then we deduct the number of cases when . That is tiresome.

Another way would be to make a series:
Case 1: there is one element in common between and .
Case2: There are two elements in common between and .
.
.
.
and so on.

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.

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.

Since the OP talks of selecting two subsets, A={1,2}, B={1} and A={1}, B={1,2} should be the same case. A slight modification of your formula takes care of that.

Originally Posted by Traveller

Since the OP talks of selecting two subsets, A={1,2}, B={1} and A={1}, B={1,2} should be the same case. A slight modification of your formula takes care of that.

You may be right in your interpretation, but the OP talks of "selecting two subsets A and B"-- so it's really not clear, at least not to me.