# How many subsets

• May 16th 2010, 03:57 PM
oldguynewstudent
How many subsets
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?
• May 16th 2010, 04:08 PM
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?
• May 16th 2010, 06:59 PM
oldguynewstudent
Quote:

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!
• May 16th 2010, 07:34 PM
Plato
Quote:

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)=?$
• May 17th 2010, 06:41 AM
oldguynewstudent
Quote:

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!