3
$\begingroup$

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 

1 Answers 1

2

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