- #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:

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- Thread starter Goldenwind
- Start date

- #1

- 146

- 0

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:

- #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

- #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

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

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

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?

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?

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

Here's a proof by induction that the number of subsets of a set with n elements has 2

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: