Help with combinations, permutations and counting please?

Printable View

February 11th 2010, 09:57 PM
chocaholic

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
February 12th 2010, 12:00 AM
lgstarn

These are tricky. Hopefully I didn't make a mistake.

Quote:

Originally Posted by chocaholic

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$ .

Quote:

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.

Quote:

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$

Quote:

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$

Quote:

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)$

Quote:

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.
February 12th 2010, 06:11 AM
Plato

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)$ .
February 13th 2010, 12:46 AM
chocaholic

Thanx

thanx a million for the input and help guys.It makes a lot more sense now.
February 23rd 2010, 09:32 AM
iva

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
February 23rd 2010, 10:44 AM
Plato

Quote:

Originally Posted by iva

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.
February 23rd 2010, 11:29 AM
iva

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!
February 23rd 2010, 11:43 AM
Plato

Quote:

Originally Posted by iva

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.