Results 1 to 5 of 5

Math Help - How many subsets

  1. #1
    Member oldguynewstudent's Avatar
    Joined
    Oct 2009
    From
    St. Louis Area
    Posts
    244

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,960
    Thanks
    1784
    Awards
    1
    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?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member oldguynewstudent's Avatar
    Joined
    Oct 2009
    From
    St. Louis Area
    Posts
    244
    Quote Originally Posted by Plato View Post
    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!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,960
    Thanks
    1784
    Awards
    1
    Quote Originally Posted by oldguynewstudent View Post
    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)=?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member oldguynewstudent's Avatar
    Joined
    Oct 2009
    From
    St. Louis Area
    Posts
    244
    Quote Originally Posted by Plato View Post
    (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!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Subsets of R^3
    Posted in the Advanced Algebra Forum
    Replies: 11
    Last Post: May 14th 2011, 02:26 AM
  2. Subsets
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: December 29th 2010, 11:33 AM
  3. Subsets
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 31st 2009, 01:48 AM
  4. Subsets
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 1st 2009, 08:54 PM
  5. Subsets
    Posted in the Math Topics Forum
    Replies: 0
    Last Post: October 22nd 2008, 01:58 AM

Search Tags


/mathhelpforum @mathhelpforum