1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Determining the number of subsets of a set with a specific property

  1. Oct 9, 2012 #1
    I found an example like the problem asks, but I'm still trying to show the first part. You want the maximum number of subsets such that you can guarantee none are pairwise disjoint.

    I'm trying to apply my specific case to the whole problem. For a set with 3 elements, I chose all of the sets with 2 elements, [itex]\binom{3}{2}[/itex] and all of the sets with 3 elements, [itex]\binom{3}{3}[/itex], which is 4 sets.

    In general, for an set with n elements, would I want to choose all sets of with n - 1 elements, which would be [itex]\binom{n}{n - 1} = n[/itex] of them and the set with n elements which there is [itex]\binom{3}{3} = 1[/itex] of them.

    But that's only n + 1 sets, when I want 2^{n - 1} sets.

    I know that [itex]\binom{n}{0} + \binom{n}{1} + \binom{n}{2} + ... + \binom{n}{n} = 2^n[/itex], which is really close to what I want to show.

    http://i3.photobucket.com/albums/y89/jdinatale/Joseph-5.png [Broken]
    Last edited by a moderator: May 6, 2017
  2. jcsd
  3. Oct 9, 2012 #2


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    For an example where equality holds for general n, consider this: how many subsets of {1,2,...,n} contain 1?

    To prove the inequality, consider this: if the collection contains a set A, can it also contain the complement of A?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook