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

Printable View

- August 18th 2011, 08:09 AMalexmahoneSubsets
We want to select two subsets A and B of [n] so that . In how many different ways can we do this?

- August 18th 2011, 12:23 PMabhishekkgpRe: Subsets
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. - August 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. - August 19th 2011, 09:22 AMTravellerRe: Subsets
- August 19th 2011, 11:35 AMawkwardRe: Subsets