Counting sets

  • Thread starter Goldenwind
  • Start date
  • #1
146
0

Homework Statement


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:

Answers and Replies

  • #2
NateTG
Science Advisor
Homework Helper
2,450
6
Can someone start me off?

How many subsets does a set with 100 elements have?
 
  • #3
HallsofIvy
Science Advisor
Homework Helper
41,847
966
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?
 
  • #4
146
0
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:
  • #5
HallsofIvy
Science Advisor
Homework Helper
41,847
966
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?
 
  • #6
146
0
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?
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
 
  • #7
HallsofIvy
Science Advisor
Homework Helper
41,847
966
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?
 

Related Threads on Counting sets

  • Last Post
Replies
2
Views
4K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
4
Views
1K
Replies
3
Views
1K
Replies
7
Views
2K
  • Last Post
Replies
17
Views
805
Replies
4
Views
1K
  • Last Post
Replies
18
Views
892
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
4
Views
3K
Top