# Trying to answer this counting question

In a ballroom dance class, participants are divided into couples for each drill session. One partner leads and the other follows for three minutes, and then the couple switches roles for the next three minutes.

(a) Only four people show up on time. How many ways are there to pair them up?

My answer here is $4C2 = \binom42 = \tfrac{4!}{2!2!}$

(b) If instead six people show up on time, how many ways are there to pair them up?

My answer here is $6C2 = \binom62 = \tfrac{6!}{4!2!}$

(c) Assume all m people in the class arrive on time. (There are an even number of people in the class.) How many ways are there to pair them up?

My answer here is $mC2 = \binom m2= \tfrac{m!}{(m-2)!2!}$

(d) Consider this time assuming that we specify which member of each couple leads first. How many ways are there to pair-and- specify the dancers

My answer here is $mP2 = \tfrac{m!}{(m-2)!}$

## UPDATE:

Part (a) the answer is $\tfrac{1}{2}(4C2 * 2C2) = 3$

Part (b) the answer is $\tfrac{1}{2}(6C2 * 4C2 * 2C2) = 45$

• Yup, they are all correct. Just a typo in the second answer, you meant 6C2, I think. – learner Dec 8 '15 at 4:15
• Yes, I corrected it, Thanks! – Coheen Dec 8 '15 at 4:16
• No, they are not correct. See theophile's answer below. – fleablood Dec 8 '15 at 4:28
• @lucidgold What is the conflict with the answers? As far as I can see, all three are saying the same thing. – Théophile Dec 8 '15 at 18:17

For part (b), the number of ways to pick a first pair, then a second pair, then a third pair, is $\binom 62 \binom 42 \binom 22$, or in your notation $6C2 \times 4C2 \times 2C2$. But that not only pairs up all the dancers but distinguishes $\{AB, CD, EF\}$ from $\{AB, EF, CD\}$, $\{CD, AB, EF\}$, and several other permutations of the pairs. In fact you have counted the same three pairs $3!$ times, which is the number of permutations of three things. So the correct answer is not to divide by $2$ but rather to divide by $3! = 6$:

$$\frac{\binom 62 \binom 42 \binom 22}{6}.$$

Part (d) seems easier to me than part (c). First you choose who will be leaders in the first part of the lesson. There are $\binom{m}{m/2}$ ways to do this. Then you line up these $m/2$ leaders in a line and assign each of the remaining $m/2$ dancers to one of the leaders. That is, each ordering of the remaining $m/2$ dancers produces a unique pairing of followers with leaders. There are $(m/2)!$ such orderings, so the total number of possible pairings is ...

Once you have part (d), I would go back to part (c). Clearly there are more pairings counted in part (d) than in part (c). How many more?

For each way you can pair up dancers in part (c), within each pair there are two ways to choose who will lead during the first part of the lesson. Since there are $m/2$ pairs, there are therefore $2^{m/2}$ ways to choose which $m/2$ dancers will lead at first. But the choice of pairs for part (c), followed by choosing leaders for the first three minutes, can give us every choice of ordered pairs that exists in part (d). Therefore the number of choices in part (c) must be ...

No, these are not quite correct—at least not the way I understand the question. When there are four people, for example, there are only three ways to pair them up: $\{AB,CD\}, \{AC,BD\}$, and $\{AD,BC\}$. The reason this is different from your answer is that you have counted how many ways there are to choose two people from a set of four. This is ${4 \choose 2} = 6$, namely, $AB, AC, AD, BC, BD, CD$. But the number of ways to form one pair isn't the same as the number of ways to split the group into pairs.

One way to do the count for part (a) is to pick one pair (as you have done), then to form a second pair from the remaining two people. The number of ways to do this is $${4 \choose 2}{2 \choose 2} = 6 \cdot 1 = 6.$$ But in doing so we have accounted for each pairing twice; e.g., we have counted both $\{AB,CD\}$ and $\{CD,AB\}$, when these are in fact the same pairing. Therefore we should divide by $2$ to get $\frac62 = 3$ pairings.

• This is a great answer. it shows the problem with part a and leaves the rest to OP. There are similar problems with the rest, but if OP understands this answer, s/he should be able to deal with the rest. If not, that is another question. This is not an easy question. – Ross Millikan Dec 8 '15 at 4:28
• So what happened if the number of people is huge like 300? Is there is any formula I can use to solve this problem? So what I understand is I should use combinations and divide the answer by 2? is this correct? – Coheen Dec 8 '15 at 4:30
• @Coheen: you asked four different questions. All your answers were not correct. If the number of people increases, yes there is a formula you can use. The answer for the first three differs greatly from the answer to the fourth. For ones like the first three, you pick one pair, then another, then another, and so on. Then you need to consider that you could pick the pairs in any order. Your formulas just pick the first pair. – Ross Millikan Dec 8 '15 at 4:36
• For part (b), would the following be correct: (6C2* 4C2* 2C2 )/2 = 45 – Coheen Dec 8 '15 at 4:56
• @Coheen The reason for dividing by two was because there were two pairs. When there are three, you should divide by 3!. This is described in more detail in David K's answer. – Théophile Dec 8 '15 at 18:16

If I am not mistaken this is applications of the Multinomial Theorem. A lot of good examples are given in Sheldon Ross's A First Course in Probability.

Also note with part $(d)$ that uniqueness matters. So if we had 4 people show up and we chose who was going to lead who we would have a permutation for all of the members dancing. For example, let the 4 people be named: John, Sally, Jordan, Steve. If John lead Steve for the first 3 minutes it would not be the same as Steve leading John. So essentially we would have the same combination below, but without the denominator in the Multinomial, since order matters.