How Many Subsets of 100 Elements Have More Than One Element?

[Goldenwind]

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?

 

[NateTG]

Can someone start me off?

How many subsets does a set with 100 elements have?

 

[HallsofIvy]

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?

 

[Goldenwind]

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:
\sum_{n=2}^{100} \left(100! - (100-n)!\right)

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

 

[HallsofIvy]

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?

 

[Goldenwind]

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. 2^n. 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

 

[HallsofIvy]

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 2ⁿ subsets. If n= 0, the set is empty- the only subset is the empty set- 1 subset= 2⁰. If n= 1, the set is {a} where a is any single element. There are 2¹= 2 subsets- { } and {a}. Now suppose "number of subsets of a set with k elements is 2^k" 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 2^k 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}: 2^k. The total number of subsets of A is 2^k+ 2^k= 2^k+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?