I have a combinatorial problem to solve, since I haven't done this for a while it would be great to get some feedback as to whether my argument is correct. Here it goes:

Suppose we have six slots and six balls to allocate (one per slot). The balls are of three different colors (so two per each color), say black (b), white (w), and red (r).

How many ways are there to allocate these balls into the slots, given that the ordering of the colors does not matter, so that for example ssbbww = bbwwss, sbswwb = wswbbs and so forth.

I argued as follows: \begin{equation} \text{There are } \binom{6}{2} \text{ ways to drop two balls of one color } \end{equation} and \begin{equation} \binom{4}{2} \text{ ways to choose the slots for the next color. } \end{equation} Dropping the remaining two balls has no freedom as only two slots are left. In order to account for the fact that the ordering of the colors (i.e. which color I choose first, second, third) does not matter I then have to divide by $3\cdot2$ as these are the number of possible ways to choose amongst three options succesively. So I get to the answer \begin{equation} \binom{6}{2}\binom{4}{2}\frac{1}{3\cdot2} = 15 \end{equation} Is that reasoning correct ? Many thanks !


That is correct! [Well, except that I don't follow precisely what the question is, the formulation is not completely unambiguous. But from the way you solve it, I presume the question is equivalent to "6 people must be divided in groups of 2 to play tennis games -- in how many ways can this be done?"]

Here is an different way to count these, using group theory. Let the group $S_6$ act on the partitions $\{\{a,b\}\{c,d\}\{e,f\}\}$ of $\{1,2,3,4,5,6\}$. (Or equivalently, on the conjugacy class of involutions without fixed points.)

The stabilizer of such a set in $S_6$ contains $3! \times 2^3$ elements: it is generated by swapping the two elements in each of the subsets, and the permutations that permute the three members of the partition.

Therefore, by the orbit-stabilizer theorem, the orbit of such a partition, and thus the number of such partitions is equal to $$ \frac{6!}{3! \times 2^3} = \frac{6\cdot 5\cdot 4}{2\cdot 2\cdot 2} = 15.$$

  • $\begingroup$ I really like the way you point to the connection to group theory, that's a great answer ! $\endgroup$ – harlekin Feb 1 '12 at 19:14

As mentioned by Myself, and now by me, the wording of the problem is unclear. There is a reasonable argument that the answer is $1$. After all, order doesn't matter!

If we are indeed dividing a group of $6$ people into $3$ teams of $2$, your way of arriving at the answer is fine. There are other ways to do it. For example, suppose these are $6$ students, and we want to divide them into $3$ study teams of $2$. Line them up in order of Student Number, or weight, whatever.

The leftmost student can choose her partner in $5$ ways. For every such choice, the first leftmost unpaired person can choose her partner in $3$ ways. Now the pairings are determined. So the total number of pairings is $(5)(3)$.

Or else let us divide $6$ people into $3$ groups of $2$ people each, and denote one member of each committee as leader, the other as follower. First choose the leaders. That can be done in $\binom{6}{3}$ ways. For every such choice, the first (oldest) leader can pick her follower in $3$ ways, and then the second can pick her follower in $2$ ways, and so on. The total number of pairings is therefore $\binom{6}{3}3!$. Each pattern of division into teams has now been counted $2^3$ times. We conclude that the team division count is $\frac{\binom{6}{3}3!}{2^3}$.

Or else we can arrange the people in order. Pair the first person with the second, the third with the fourth, the fifth with the sixth. There are $6!$ ways to line up the people. However, this vastly overcounts the number of divisions into teams.

For if in a permutation we interchange the first and the second, and/or the third with the fourth, and or the fifth with the sixth, we get the same division into teams. this gives an overcount factor of $2^3$. But we also get the same division into teams from, for example, permutation $352146$ as from $214635$ (permute the contiguous groups of two, without changing the order in each group), for a further overcount factor of $3!$. Thus the answer to the original question is $\frac{6!}{2^3 3!}$.

  • $\begingroup$ great, many thanks for giving the various approaches! That really helps to see the underlying process more clearly. $\endgroup$ – harlekin Feb 1 '12 at 19:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.