Thread: My Problem

  1. #1
    Microsoft Lover afreedboy's Avatar
    Join Date
    Nov 2003
    Posts
    189

    My Problem

    I have one problem that I can't solve. I am thinking about it for a week.

    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.


  2. #2
    Administrator webmaster's Avatar
    Join Date
    Aug 2001
    Posts
    1,012
    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.)

  3. #3
    Microsoft Lover afreedboy's Avatar
    Join Date
    Nov 2003
    Posts
    189
    Thanks a lot!!!

    But I have another question. Please help me also.


    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.

  4. #4
    Administrator webmaster's Avatar
    Join Date
    Aug 2001
    Posts
    1,012
    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.

  5. #5
    Microsoft Lover afreedboy's Avatar
    Join Date
    Nov 2003
    Posts
    189
    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 ?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need help understanding a problem
    By dnguyen1022 in forum C++ Programming
    Replies: 2
    Last Post: 04-29-2009, 04:21 PM
  2. Memory problem with Borland C 3.1
    By AZ1699 in forum C Programming
    Replies: 16
    Last Post: 11-16-2007, 11:22 AM
  3. Someone having same problem with Code Block?
    By ofayto in forum C++ Programming
    Replies: 1
    Last Post: 07-12-2007, 08:38 AM
  4. A question related to strcmp
    By meili100 in forum C++ Programming
    Replies: 6
    Last Post: 07-07-2007, 02:51 PM
  5. WS_POPUP, continuation of old problem
    By blurrymadness in forum Windows Programming
    Replies: 1
    Last Post: 04-20-2007, 06:54 PM