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

In summary, the conversation discussed the number of subsets of a set with 100 elements that have more than one element, taking into account the empty set and the order of elements. The final conclusion is that there are 2^n subsets, where n represents the number of elements in the set.
  • #1
Goldenwind
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:
Physics news on Phys.org
  • #2
Goldenwind said:
Can someone start me off?

How many subsets does a set with 100 elements have?
 
  • #3
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
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
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
HallsofIvy said:
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
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 to How Many Subsets of 100 Elements Have More Than One Element?

1. How do you calculate the number of subsets with more than one element from a set of 100 elements?

The number of subsets with more than one element from a set of 100 elements can be calculated using the formula 2100 - 101, which equals 2100 - 1, or approximately 1.2676506 x 1030 subsets.

2. What is the significance of having more than one element in a subset?

Having more than one element in a subset allows for greater variability and combinations within the set. This can be useful in various mathematical and scientific applications, such as probability and data analysis.

3. Can you give an example of a subset with more than one element from a set of 100 elements?

One example of a subset with more than one element from a set of 100 elements could be a subset of all even numbers from 1 to 100, which would include 50 elements.

4. How does the number of subsets with more than one element change as the size of the set increases?

The number of subsets with more than one element increases exponentially as the size of the set increases. For every additional element added to the set, the number of subsets with more than one element doubles.

5. Are there any practical applications for calculating the number of subsets with more than one element?

Yes, there are many practical applications for calculating the number of subsets with more than one element. Some examples include analyzing data sets, determining probabilities in statistics, and solving problems in combinatorics and graph theory.

Similar threads

  • Calculus and Beyond Homework Help
Replies
1
Views
551
  • Calculus and Beyond Homework Help
Replies
3
Views
1K
  • Calculus and Beyond Homework Help
Replies
11
Views
2K
  • Calculus and Beyond Homework Help
Replies
7
Views
1K
  • Calculus and Beyond Homework Help
Replies
15
Views
1K
  • Calculus and Beyond Homework Help
Replies
4
Views
2K
  • Calculus and Beyond Homework Help
Replies
17
Views
1K
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
  • Calculus and Beyond Homework Help
Replies
24
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
942
Back
Top