How many subsets

**oldguynewstudent** · May 16th 2010, 02:57 PM

I am totally guessing at this one.

Let k and n be positive integers satisfying k < n. How many subsets of [n] are not also subsets of [k]?

Take k=2 and n=3, then

[3] = { $\phi$ } {1} {2} {3} {1,2} {1,3} {2,3} {1,2,3}

[2] = { $\phi$ } {1} {2} {1,2}

The cardinality of [3] = $2^3$ and the cardinality of [2] = $2^2$ . The number of subsets of [3] that are not subsets of [2] = $2^3$ - $2^2$ .

So I think the number of subsets of [n] that are not also subsets of [k] would be $2^n$ - $2^k$ . Is this correct?

**Plato** · May 16th 2010, 03:08 PM

Take any non-empty subset of $[n]\setminus[k]$ and unite it with any subset of $[k]$ .
That will be one of your required subsets.
What do you get?

**oldguynewstudent** · May 16th 2010, 05:59 PM

Originally Posted by Plato

Take any non-empty subset of $[n]\setminus[k]$ and unite it with any subset of $[k]$ .
That will be one of your required subsets.
What do you get?

I'm sorry but I don't understand why you would unite $[n]\setminus[k]$ with $[k]$ . Don't we just want to count the subsets for $[n]\setminus[k]$ ?

The neurons are willing but the dendrites are weak!

**Plato** · May 16th 2010, 06:34 PM

Originally Posted by oldguynewstudent

I'm sorry but I don't understand why you would unite $[n]\setminus[k]$ with $[k]$ . Don't we just want to count the subsets for $[n]\setminus[k]$ ?

The neurons are willing but the dendrites are weak!

$(2^{n-k}-1)(2^k)=?$

**oldguynewstudent** · May 17th 2010, 05:41 AM

Originally Posted by Plato

$(2^{n-k}-1)(2^k)=?$

OK, I had to go back and review set theory again.

First I made a mistake with { $\phi$ }. It should just be $\phi$ .

I see the algebra of exponents gives the same answer that I originally came up with $(2^{n-k}-1)(2^k)=2^n - 2^k$ .

Also when you unite any non-empty subset of [k] with [n]\[k] you still get [n]\[k]. I suppose the only reason to go to all that trouble would be to eliminate the null set?

Trying to use the force, but this little green guy keeps whacking me with his light saber!

Thread: How many subsets

LinkBack

Thread Tools

Display

How many subsets

Similar Math Help Forum Discussions

Subsets of R^3

Subsets

Subsets

Subsets

Subsets

Search Tags