Counting Problem: A group of 30 people consists of 15 women and 15 men, How many ways to:

Question

Hi I am really having trouble trying to work out:

A group of 30 people consists of 15 women and 15 men, How many ways to:

1. form 10 pairs from the group?

2. divide the group into two groups (group 1 and group 2) of equal size?

3. divide the group into 2 equal groups, where each group in its own has as many men as women in it?

4. divide the groups into two groups of equal size such that group 1 contains at least 4 men?

5. divide the group into two groups, each having size at least one?

My answers: say $p_1, p_2,...,p_{30} \in$ group of 30 people

1)Not sure at all about this one, but I know that it is not ${30\choose 2}*{28\choose 2}*…*{10\choose 2}$ as there will be double counting.

2) ${30 \choose 15}$

Reasoning: Form groups of size 15. thus if group1 is $p_1,p_2,...,p_{15}$ then group2 would be $p_{16},p_{17},...,p_{30}$. Thus effectively dividing the group into 2 groups of equal size. I believe that each group is NOT arbitrary? so if another case: if group1 is $p_{16},p_{17},...,p_{30}$ then group2 would be $p_1,p_2,...,p_{15}$ this what we want and not double counting. Is this what they are asking?

3)Not to sure about this one, as we can make 15 packs of 1 man and 1 woman, but 15/2 does not make sense here, thus I suppose the best we can do is have 2 groups with 7 men and 7 women: ${15 \choose 7} * {15\choose 7}$ but this is not fully dividing the group.

Reasoning: pick 7 men from 15 and 7 women form 15. $m_1,m_2,...,m_7,w_1,w_2,...,w_7$. Are the groups arbitrary? and thus answer is: ${15 \choose 7} * {15\choose 7}/2$

4)${30\choose 15} - {18\choose 15}$

Reasoning: get all the ways to divide the group in half, then remove all the cases where the is not at least 4 men in group

5)if arbitrary groups: ${30\choose 1}+{30\choose 2}+...+{30\choose 15}$if not arbitrary groups:${30\choose 1}+{30\choose 2}+...+{30\choose 29}$

Reasoning: add the number of ways to form a group of size 1, to the number of ways to form a group of size 2, to.... I only do to ${30\choose 15}$ if they are asking for arbitrary groups or there would be double counting,

This is all the information that they give regarding the questions, and I am so lost. like for question 3, what determines the group size, if they want 15: 15, then it not possible.

I would greatly appreciate any help that you can offer to help me to understand how to answer these questions

Answer 1

A group of $30$ people consists of $15$ women and $15$ men. In how many ways can $10$ pairs be formed from the group?

$$\binom{30}{2}\binom{28}{2}\binom{26}{2}\binom{24}{2}\binom{22}{2}\binom{20}{2}\binom{18}{2}\binom{16}{2}\binom{14}{2}\binom{12}{2}$$ is the number of ways of selecting ten labeled pairs of two people from the group. Since the groups are not labeled, we must divide by the $10!$ ways we could select the same ten pairs of people, so the number of ways $10$ pairs could be formed from the group is $$\frac{1}{10!}\binom{30}{2}\binom{28}{2}\binom{26}{2}\binom{24}{2}\binom{22}{2}\binom{20}{2}\binom{18}{2}\binom{16}{2}\binom{14}{2}\binom{12}{2}$$

A group of $30$ people consists of $15$ women and $15$ men. In how many ways can the group be divided into two groups of equal size?

Your answer $$\binom{30}{15}$$ is correct if the groups are labeled, which I believe is the author's intent since the question refers to group 1 and group 2.

If the groups were unlabeled, we would have to divide by the $2!$ ways we could select the same two groups of $15$ people, so there would be $$\frac{1}{2!}\binom{30}{15}$$ ways to divide the group of $30$ people into two unlabeled groups of $15$ people.

A group of $30$ people consists of $15$ women and $15$ men. In how many ways can the group be divided into two groups of equal size, where each group has an equal number of men and women in it?

Since there are an odd number of men and an odd number of women, this is impossible.

A group of $30$ people consists of $15$ women and $15$ men. In how many ways can the group be divided into two groups of equal size such that group 1 has at least four men?

The problem indicates that the groups are labeled, so there would be $\binom{30}{15}$ ways of selecting the members of group 1 if there were no restrictions. From these selections, we must subtract those cases in which there are fewer than four men in group 1. A group of $15$ people with exactly $k$ men can be selected from $15$ men and $15$ women in $$\binom{15}{k}\binom{15}{15 - k}$$ ways. Hence, the number of ways we could select a group with fewer than four men is $$\binom{15}{0}\binom{15}{15} + \binom{15}{1}\binom{15}{14} + \binom{15}{2}\binom{15}{13} + \binom{15}{3}\binom{15}{12}$$ Therefore, the number of ways of dividing the group of $30$ people into two labeled groups of $15$ people if group 1 has at least four men is $$\binom{30}{15} - \binom{15}{0}\binom{15}{15} - \binom{15}{1}\binom{15}{14} - \binom{15}{2}\binom{15}{13} - \binom{15}{3}\binom{15}{12}$$

A group of $30$ people consists of $15$ women and $15$ men. In how many ways can the group be divided into two groups, each having size at least $1$?

Observe that the groups are not labeled.

Suppose Amy is one of the women. For each of the remaining $29$ people, we have two choices: We can either place a person in Amy's group or the other group. That gives us $2^{29}$ divisions into two groups. However, we are prohibited from placing all $29$ of the other people in the same group as Amy since then the other group would be empty. Hence, there are $2^{29} - 1$ ways to divide the groups into two groups, each with size at least one.

Answer 2

I really like @N.T.Taussig's post. However, for the sake of the argument, I'd like to add a second method to obtain the last answer.

By reading the previous answers, we understand that if we label the groups, the answer is $$ \sum_{k=1}^{n-1} {n\choose k} = \sum_{k=0}^{n} {n\choose k} -{n\choose n} - {n\choose 0} = \sum_{k=0}^{n} {n\choose k} -2 $$ So, we have to come up with a clever way to sum the binomial coefficients. This is done by using Binomials theorem, $ (X+Y)^n = \sum_{k=0}^n {n\choose k}X^kY^{n-k} $ , and choosing $X=1=Y$. This simplifies Binomials theorem to $$ 2^n = \sum_{k=0}^n {n\choose k} $$ Therefore, the answer is $2^n -2$, if we label the two groups. If we do not label the groups, we have to account for the double counting. Hence, we obtain $2^{n-1} -1$. This is of course the same result as N. T. Taussig obtained.