3
$\begingroup$

How many ways can 11 people be divided into three teams where each team must have at least two members?

We are supposed to use multinomial coefficients and number of integer solutions. I have tried this The number of ways to divide 5 people into three groups and this Arranging $10$ people in $2$ lanes. Each lane has to have at least $2$ people. and more specifically this Number of ways to divide n people into k groups with at least 2 people in each group, but the last one in particular I could not understand at all (since I do not know what the brackets { } mean).

I have tried several things so far, but I am not convinced any of them are correct. Here is my best attempt:

If each group has at least two people, I initially choose 6 from 11: $$\binom{11}{6}=42$$

Then, these 6 people need to be put in the groups of 2 people: $$\frac{6!}{2!2!2!}=90$$ But, since order does not matter, we must divide by 3!: $$\frac{6!}{2!2!2!3!} = 15$$

So for the choice of the two people in each group we have 90*15 = 1350 possibilities.

Now we need to consider the 5 remaining people. Let $x_1,x_2,x_3$ be the number of people in each group. Then we have a total of $$\binom{5+3-1}{3-1} = \binom{7}{2}=21$$ (non negative) integer solutions for $x_1+x_2+x_3=5$.

However, the possible cases are: $$(0,1,4),(0,2,3),(0,0,5),(1,1,3),(1,2,2),$$ where the first two triplets appear a total of 3! each (order does not matter) and the last three apear $\frac{3!}{2!} =3$ times (due to permutation of terms with same amount of people).

Case $(0,1,4)$: $\binom{5}{1}\binom{4}{4}=5,$ giving a total of $3!5 = 30$ possibilities.

Case $(0,2,3)$: $\binom{5}{2}\binom{3}{3}=10,$ giving a total of $3!10 = 60$ possibilities.

Case $(0,0,5)$: $\binom{5}{5}=5,$ giving a total of $3\times 5 = 15$ possibilities.

Case $(1,1,3)$: $\binom{5}{1}\binom{4}{1}\binom{3}{3}=2,0$ giving a total of $3\times 20 = 60$ possibilities.

Case $(1,2,2)$: $\binom{5}{1}\binom{4}{2}\binom{2}{2}=6,$ giving a total of $3\times 6 = 18$ possibilities.

Then we will have a total of $1350(30+60+15+60+18) = 247050$ possibilities.

Can anyone help with the logical reasoning here to see if this is correct? In case it is wrong, where am I going wrong?

$\endgroup$
  • $\begingroup$ Are the groups distinct per se, or would (say) $AB,CD$ and $CD,BA$ be treated as the same division? $\endgroup$ – Parcly Taxel Jul 4 '19 at 13:47
  • $\begingroup$ I am assuming they are treated as the same division: (AB),(CD),(EF) = (CD),(AB),(EF) and so on. $\endgroup$ – MsWynfled Jul 4 '19 at 14:06
2
$\begingroup$

It is ill-advised to treat the compulsory two people in each group separately. Rather, the partitions of $11$ into $3$ with each part at least $2$ should be looked at directly, which as you have worked out are $$(7,2,2),(6,3,2),(5,4,2),(5,3,3),(4,4,3)$$ These lead to the following counts for each partition.

  • $(7,2,2)\to\binom{11}7\binom42/2=990$ ways
  • $(6,3,2)\to\binom{11}6\binom53=4620$
  • $(5,4,2)\to\binom{11}5\binom64=6930$
  • $(5,3,3)\to\binom{11}5\binom63/2=4620$
  • $(4,4,3)\to\binom{11}3\binom84/2=5775$

The division by $2$ in three of the cases accounts for the indistinguishability of groups with the same people but different positions. Adding the counts up, there are $22935$ admissible partitions.

$\endgroup$
  • $\begingroup$ I think I got it. Just one question now: in exercises like this, do I really have to look into all partitions or is there a "simpler" way to do it? I mean, this is really simple, but if we have more people to be divided in more groups with at least two people, than the number of partitions increases a lot.But thanks for showing where I'm going wrong. $\endgroup$ – MsWynfled Jul 4 '19 at 14:25
  • $\begingroup$ @MsWynfled Yes, all partitions have to be considered. $\endgroup$ – Parcly Taxel Jul 4 '19 at 14:34
1
$\begingroup$

Looking at the number of persons in the groups we discern the following possibilities:

  • for $(2,2,7)$ there are $\frac{11!}{2!2!7!}\cdot\frac12$ possibilities.
  • for $(2,3,6)$ there are $\frac{11!}{2!3!6!}$ possibilities.
  • for $(2,4,5)$ there are $\frac{11!}{2!4!5!}$ possibilities.
  • for $(3,3,5)$ there are $\frac{11!}{3!3!5!}\cdot\frac12$possibilities.
  • for $(3,4,4)$ there are $\frac{11!}{3!4!4!}\cdot\frac12$ possibilities.

Note the factor $\frac12$ in the cases where exactly two groups have the same size.

This factor repairs double counting.

In all other cases the groups are distinguishable by the number of members.

The summation of these numbers is the answer on your question.

$\endgroup$

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.