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?

Printable View

- Aug 18th 2011, 08:09 AMalexmahoneSubsets
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 PMabhishekkgpRe: 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 PMawkwardRe: 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 AMTravellerRe: Subsets
- Aug 19th 2011, 11:35 AMawkwardRe: Subsets