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: Counting sets

  1. Mar 6, 2008 #1
    1. The problem statement, all variables and given/known data
    How many subsets of a set with 100 elements have more than one element?

    The thing throwing me off here is the zero-set, and whether it counts as an element or that. Can someone start me off?
     
    Last edited: Mar 6, 2008
  2. jcsd
  3. Mar 6, 2008 #2

    NateTG

    User Avatar
    Science Advisor
    Homework Helper

    How many subsets does a set with 100 elements have?
     
  4. Mar 6, 2008 #3

    HallsofIvy

    User Avatar
    Science Advisor

    No, the "zero-set", by which I assume you mean the empty set, does not count as an "element", it counts as a subset. Can you answer NateTG's question: How many subsets (without any restrictions) does a set of 100 elements have? The only subset with no elements is the empty set. How many subsets with exactly one element?
     
  5. Mar 6, 2008 #4
    A subset could have none (Empty set, 1 possibility)
    A subset could have 1 (100 possibilities)
    A subset could have 2 (100 possibilities for the first element, 99 for the next)
    ...but then does the order of elements count? Is 1,2 the same as 2,1? Going to assume it's the same.

    A subset with 3 elements has 100 for the first, 99 for the second, 98 for the third...

    So, counting only subsets with more than 1 element, what we're looking at is:
    [tex]\sum_{n=2}^{100} \left(100! - (100-n)!\right)[/tex]

    Edit: I think my formula is wrong, actually, as it doesn't work for n=100. Either way, it'd be hell to compute :P
     
    Last edited: Mar 6, 2008
  6. Mar 6, 2008 #5

    HallsofIvy

    User Avatar
    Science Advisor

    Your calculation isn't correct because you are counting, for example, {a, b, c} as different from {b, a, c} or {c, b, a}.

    A set with 0 elements has 1 subset: the empty set itself: { }.
    A set with 1 element, a, has 2 subsets: the empty set and the whole set:{ }, {a}.
    A set with 2 elements, a, b, has 4 subsets: { }, {a}, {b}, and {a,b}.
    a set with 3 elements, a, b, c, has 8 subsets: { }, {a}, {b} {c}, {ab}, {ac}, {bc}, {abc}.
    Do you see the pattern?
     
  7. Mar 6, 2008 #6
    I see the pattern. [itex]2^n[/itex]. But if our 100-element set had a, b, c, d, etc.... wouldn't a subset with just 'a', and one with just 'b', be different subsets?

    You've always been informative in the past, so I trust your word, but just questioning such that I can understand. :)

    Edit: WOAH, quotes just went wonky. Updated? Awesome :D
     
  8. Mar 6, 2008 #7

    HallsofIvy

    User Avatar
    Science Advisor

    Yes, {a} and {b} are different subsets- and I listed and counted them as different. My point was that {a, b} and {b, a} are NOT and your method was counting both.

    Here's a proof by induction that the number of subsets of a set with n elements has 2n subsets. If n= 0, the set is empty- the only subset is the empty set- 1 subset= 20. If n= 1, the set is {a} where a is any single element. There are 21= 2 subsets- { } and {a}. Now suppose "number of subsets of a set with k elements is 2k" for some k> 0. Let A be a set containing n+1 elements. Pick an element of A- call it "a". Every subset of A either contains a or not. If it does not contain a, then it is a subset of A-{a} which has k elements and so 2k subsets. If it does contain a, then it equal to a subset of A-{a} union {a} and so there are exactly as many of them as subsets of A- {a}: 2k. The total number of subsets of A is 2k+ 2k= 2k+1.

    Now you know that there is exactly 1 subset containing no elements: the empty set.
    How many subsets of a 100 member set are there that contain exactly on element?

    How many subsets are left that contain more than one element?
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook