# Subsets

• Aug 18th 2011, 08:09 AM
alexmahone
Subsets
We want to select two subsets A and B of [n] so that \$\displaystyle A \cap B \neq\emptyset\$. In how many different ways can we do this?
• Aug 18th 2011, 12:23 PM
abhishekkgp
Re: Subsets
First we find how many ways are there to choose two subsets \$\displaystyle A\$ and \$\displaystyle B\$ of \$\displaystyle [n]\$ without worrying about what their intersection is.

There are \$\displaystyle 2^{2n}\$ ways of doing this.
Then we deduct the number of cases when \$\displaystyle A \cap B=\Phi\$. That is tiresome.

Another way would be to make a series:
Case 1: there is one element in common between \$\displaystyle A\$ and \$\displaystyle B\$.
Case2: There are two elements in common between \$\displaystyle A\$ and \$\displaystyle B\$.
.
.
.
and so on.
• Aug 18th 2011, 04:53 PM
awkward
Re: Subsets
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.
• Aug 19th 2011, 09:22 AM
Traveller
Re: Subsets
Quote:

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.
• Aug 19th 2011, 11:35 AM
awkward
Re: Subsets
Quote:

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.