Results 1 to 8 of 8

Math Help - Help with combinations, permutations and counting please?

  1. #1
    Junior Member
    Joined
    Feb 2010
    Posts
    54

    Question Help with combinations, permutations and counting please?

    A group of 30 people consists of 15 women and 15 men.
    How many ways are there to:
    1) Pair the women and men off?( I got 15! as the first guy has 15 women to choose from , the second has 14 etc. is this correct?)
    2) Form 10 pairs from the group? (This is non-gender specific so you first choose 20 People from the group =C(30,20)? but what do you multiply it with to get the pairs? Or am I completely wrong about the first half?)
    3) Divide the group into two groups (group 1 and 2) of equal size? (Is this just choosing 15 people from 30 = C(30,15)?)
    4) Divide the group into two equal groups, where each group in its own has as many women as men in it? (would this be taking 7 men from 15 and multiplying it by taking 7 women from 15? I'm now officially lost and hopelessly confused?)
    5) Divide the group into two groups of equal size, such that group 1 contains at least 4 men? (I don't have a clue. Choose 15 from 30 people multiplied by C(15,4)?)
    6) Divide the group into two groups each having size at least 1?(C(30,1)?)

    Help with formulae and explanations would help majorly. Thanks in advance
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Feb 2010
    Posts
    29
    These are tricky. Hopefully I didn't make a mistake.

    Quote Originally Posted by chocaholic View Post
    A group of 30 people consists of 15 women and 15 men.
    How many ways are there to:
    1) Pair the women and men off?( I got 15! as the first guy has 15 women to choose from , the second has 14 etc. is this correct?)
    Yes. The answer is 15! = 1307674368000.

    2) Form 10 pairs from the group? (This is non-gender specific so you first choose 20 People from the group =C(30,20)? but what do you multiply it with to get the pairs? Or am I completely wrong about the first half?)
    Once you've chosen your 20 people, you now have to count the number of ways to pair these people, which is C(20,2). So it should be C(30,20)C(20,2).

    Recall that C(n,k) is the number of ways to choose k objects from n when the ordering doesn't matter. If there is more than one grouping step, multiply by the number of ways each step can be done.

    3) Divide the group into two groups (group 1 and 2) of equal size? (Is this just choosing 15 people from 30 = C(30,15)?)
    Here, dividing the group into two means that if you have (A,B,C,D,E,F), choosing (A,B,C) is the same as choosing (D,E,F). So you have to divide by 2 to get rid of the duplicates.

    So the number of ways to divide into two groups is C(30,15)/2.

    The question is a bit confusing though, especially in light of the next question...

    Perhaps what is meant is how many ways to make two groups of equal size? That is to say, you can have a group of 1 and 1, a group of 2 and 2, a group of 3 and 3, etc. In that case you would have

    C(30,2)C(2,1)/2 + C(30,4)C(4,2)/2 + C(30,6)C(6,3)/2 + \ldots + C(30,30)C(30,15)/2

    4) Divide the group into two equal groups, where each group in its own has as many women as men in it? (would this be taking 7 men from 15 and multiplying it by taking 7 women from 15? I'm now officially lost and hopelessly confused?)
    This doesn't make sense. If you have a group of 15 with 7 women, you will have 8 men and vice versa. So I don't see how each group can have as many men as women.

    If you allow for groups of 2, 4, 6, etc., and you have a group with an even number in each group, you can have an equal number of men and women. So, following the last problem, you would have

    C(30,4)C(4,2)/2 + C(30,8)C(8,4)/2 \ldots + C(30,28)C(30,14)/2

    5) Divide the group into two groups of equal size, such that group 1 contains at least 4 men? (I don't have a clue. Choose 15 from 30 people multiplied by C(15,4)?)
    Hmm. Only group 1 needs 4 men?

    Well, we can take what we had before and modify it. First of all, clearly we can't have any group with less than 4 members. So the number of ways to create two equal groups with more than 4 members is:

    \left(C(30,8)C(8,4) + C(30,10)C(10,5) + C(30,12)C(12,6) \ldots + C(30,30)C(30,15)\right)/2

    Now we're in a bit of trouble because it does matter if they go into group 1 versus group 2. So we need to count the ways to put 4/15 men in group 1 and then we can choose the rest of the groups freely. The number of ways to choose 4 men to be in the group of size 6 is

    C(15,4)C(26,2)C(24,6)

    because we have to choose 4 men from 15, then we can choose the remaining 2 from any of the 26 left to make up the rest of the group, and then we can choose any 6 of the remaining 24 for group 2. So we have

    C(15,4)C(26,0)C(26,4) + C(15,4)C(26,1)C(25,5) + \ldots + C(15,4)C(26,11)C(15,15)

    6) Divide the group into two groups each having size at least 1?(C(30,1)?)
    Now we don't have a size requirement on the groups.

    So you can have a group of (1,1), (1,2), \ldots (1,29), (2,2), (2,3), \ldots (2,28), \ldots (15,15)

    So that gives us

    (C(30,2)C(2,1) + C(30,3)C(3,2) + \ldots+ C(30,30)C(30,28)
     + \ldots + C(30,30)C(30,15))/2

    I think these are right. But these kinds of problems are always really, really tricky so I could be wrong.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,966
    Thanks
    1785
    Awards
    1
    With respect to #2, the number of ways to group twenty people into ten pairs is \frac{20!}{2^{10}(10!)}.
    That is known as unordered partitions. That number is much greater than C(20,2).
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Feb 2010
    Posts
    54

    Thumbs up Thanx

    thanx a million for the input and help guys.It makes a lot more sense now.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    iva
    iva is offline
    Member iva's Avatar
    Joined
    Nov 2009
    From
    South Africa
    Posts
    81

    Hi there, I got different answers for 1 and 2:

    For 1, I got 15!15! as for each and every man there is 15 possible female partners ie
    15 (15). 14(14). 13 (13).... 1 (1) = 15!15! , i think its logic follows from the problem here: http://www.mathhelpforum.com/math-he...ake-sense.html

    For 2 ( i haven't covered unordered partitions yet ), but i used the same thinking as lgstarn further up ie First you have to choose your 20 people C(30,20), Then pair them off ie C(20,2) and multpily the 2 answers? The only problem with this is that the number i get is huge:
    (30C20)( 20C2) = 30045015 (190) = 5708552850. Can this be right?s
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,966
    Thanks
    1785
    Awards
    1
    Quote Originally Posted by iva View Post
    Hi there, I got different answers for 1 and 2:
    For 1, I got 15!15! as for each and every man there is 15 possible female partners ie 15 (15). 14(14). 13 (13).... 1 (1) = 15!15! , i think its logic follows from the problem here:

    For 2 ( i haven't covered unordered partitions yet ), but i used the same thinking as lgstarn further up ie First you have to choose your 20 people C(30,20), Then pair them off ie C(20,2) and multpily the 2 answers? The only problem with this is that the number i get is huge: (30C20)( 20C2) = 30045015 (190) = 5708552850. Can this be right?s
    If we were to form a queue of the 30 people alternating men and women then the number of ways that can be done is 2\cdot (15!)^2.
    But that is not equivalent to what is being asked here.
    Think of a roster of 15 men listed in alphabetical order. We have 15 women each can be assigned to one and only one of the men on the list. That can be done in 15! ways.
    That is the nature of this question.

    As for #2 there are \frac{30!}{(20!)(10!)}\cdot \left(\frac{20!}{2^{10}(10!)}\right) ways to pair 20 chosen from 30 is a gender neutral way.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    iva
    iva is offline
    Member iva's Avatar
    Joined
    Nov 2009
    From
    South Africa
    Posts
    81
    Thank you I understand 1 now but not 2 , guess this is somethign still coming up in my textbook as I have never seen that exponent used yet. I don't get why we use 20!/(2^10)( 10!) in place of 20!/2!18!
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,966
    Thanks
    1785
    Awards
    1
    Quote Originally Posted by iva View Post
    I don't get why we use 20!/(2^10)( 10!) in place of 20!/2!18!
    Well, we don't do that.
    \binom{20}{2}=\frac{20!}{2!\cdot 18!} is the number of ways to get one pair from twenty people.

    On the other hand, there are \frac{20!}{2^{10}(10!)} ways to form ten pairs from twenty people.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Counting (Permutations/Combinations)
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 12th 2010, 10:49 PM
  2. Replies: 1
    Last Post: March 25th 2010, 08:38 AM
  3. Counting (Permutations & Combinations)
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 29th 2009, 06:06 PM
  4. Counting (Permutations and Combinations)
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 25th 2009, 05:34 PM
  5. Counting, permutations and/or combinations
    Posted in the Statistics Forum
    Replies: 4
    Last Post: March 27th 2008, 06:44 PM

Search Tags


/mathhelpforum @mathhelpforum