# My Problem

• 12-31-2003
afreedboy
My Problem
I have one problem that I can't solve. I am thinking about it for a week.

Quote:

How many subsets with more than two elements can take out from a set with 100 elements??
I know the answer is 2( power 100) - 5051

I don't know why substract 5051 ???
For 2 power 100 is I think because of two elements from 100 elements.

:confused:
• 12-31-2003
webmaster
The total number of subsets of a set of size N is 2^N, and the total number of subsets of size 1 is (obviously) 100, and the total number of subsets of size 0 is (obviously) 1, and the total number of subsets of size 2 is (not so obviously) 100*99/2 = 9900/2 = 4950. So you add the numbers together to get 4950 + 100 + 1 = 5051. So that's how many subsets of size less than 2 there are.

So why is it 100*99/2 for sets of size 2? Well, think of it as though you are filling two positions, A and B. Position A can be filled by any of the 100 elements, and position B can be filled by any of the remaining 99 elements. So you have 99*100 ways of filling A and B; but since we are talking about sets, which are unordered, then we need to divide by 2. (For instance, A=1, B=2 and B=2, A=1 are equivalent because the subset doesn't care how we order it; it only cares about its elements. If it cares about anything at all. I've heard of some particularly nasty subsets that feel rather empty.)
• 12-31-2003
afreedboy
Thanks a lot!!!

The total ways for eight men and five women to stand in a line to make no two women stand next to each other = 609,638,400

But for a bit strings contain eight 0s and ten 1s for every 0 must be immediately followed by a 1 = only 45

What is the difference???
My discrete exam is on next week. Please don't mind me. I need you guys' help a lot. :(
• 01-01-2004
webmaster
Without checking any of the math involved, my guess would be that a binary number is an inappropriate model for the situation with a line of men and women, since each man or woman is an individual, whereas all 0s or all 1s are the same. (Say you had one man and two women, for instance, and the women could not stand next to each other in line. In that case, if 1 is equivalent to man and 0 to woman, then you could only have 010; but you have two possible lineups, each with the two women in different places.)

So the difference is that for each string or 0s and 1s, you are in fact representing many possible orders of men and women.
• 01-01-2004
afreedboy
Can I get your yahoo Id, webmaster ?? So I can discuss with you on messenger.

How about containing at least three 0s and at least three 1s in bit strings of length ten ?