Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a group of 6 objects, that I want to put into 2 groups of 3. I know there are 20 combinations, but simultaneously there are only 10 combinations as the others are redundant. How do I programatically (probably using functions from igraph??) develop a general solution? Ultimately, I'll want to take a group of 40 objects and put them in groups of 10. The table below illustrates all the unique simultaneous sets for 2 groups of 6 objects.

a b c  |  d e f  |  001
a b d  |  c e f  |  002
a b e  |  c d f  |  003
a b f  |  c d e  |  004
a c d  |  b e f  |  005
a c e  |  b d f  |  006
a c f  |  b d e  |  007
a d e  |  b c f  |  008
a d f  |  b c e  |  009
a e f  |  b c d  |  010
share|improve this question

1 Answer 1

We want to divide $kn$ people into $k$ groups of $n$ people.

Line up the $kn$ people by order of student number.

The person with the lowest student number gets to pick her team. She has $\dbinom{kn-1}{n-1}$ choices. Now the unchosen person with the lowest student number gets to pick her team. She has $\dbinom{(k-1)n-1}{n-1}$ choices. Now the unchosen person with the lowest student number gets to pick her team. She has $\dbinom{(k-2)n-1}{n-1}$ choices. And so on. Multiply.

Another way: Let us divide our $kn$ people into $k$ teams, one of which is to wear uniforms of colour $C_1$, one to wear uniforms of colour $C_2$, and so on. It is easy to see that this can be done in $\dbinom{kn}{n!,n!,\dots,n!}$ ways.

Here we used the multinomial coefficient, which simplifies to $\dfrac{(kn)!}{(n!)^k}$.

Now the teams stay intact, but decide to play their sport at a nudist camp, and shed their uniforms. Then the $k!$ permutations of uniform colour collapse into one. Thus the number of divisions into $k$ uniformless teams is $\dfrac{1}{k!}\dfrac{(kn)!}{(n!)^k}$.

For the toy example $k=2$, $n=3$, the first method gives $\binom{5}{2}$. The second gives $\frac{1}{2!}\binom{6}{3,3}$. Each of these is $10$.

For $40$ people and groups of $10$, the first approach gives $\binom{39}{9}\binom{29}{9}\binom{19}{9}$.

The second approach gives $\frac{1}{4!}\frac{40!}{(10!)^4}$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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