1. Not finding help here? Sign up for a free 30min 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!

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
    Staff Emeritus
    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
    Staff Emeritus
    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
    Staff Emeritus
    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?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?