How many ways can you divide $9$ students into three unlabeled teams where one team contains $4$ people, one contains $3$ people and the last contains $2$ people? Unlabeled, meaning that groups with abc = bca = cba, etc
I understand how to do this if the teams are labeled:
$$\frac{9!}{4!3!2!}$$
But there is a term missing in the denominator when the teams are unlabeled and I'm having difficulty understanding how to calculate how many ways the teams can be organized.
There are $3!$ ways to organize the same first group of $3$, $4!$ ways to organize the same second group of $4$ and $2!$ ways to organize the last group of $2$. Why wouldn't you multiply $3!4!2!$ in the denominator?
For instance:
(ABC, DEFG) = (ABC, DEGF) = (ABC, DFEG) = (ACB, DFGE), etc
Best Answer
The teams are distinguished by their sizes. Choosing who is on each team completely determines the teams.
There are $\binom{9}{4}$ ways to select four of the nine students to be on the team of four students, $\binom{5}{3}$ to select three of the five remaining students to be on the team with three students, and one way to form a team of two from the remaining two students. Hence, there are $$\binom{9}{4}\binom{5}{3} = \frac{9!}{4!5!} \cdot \frac{5!}{3!2!} = \frac{9!}{4!3!2!}$$ ways to divide the nine students into three unlabeled teams.
If we had instead chosen the team of two, then the team of three from the remaining seven students, and then placed the remaining four students on the team of four, we could select the teams in $$\binom{9}{2}\binom{7}{3} = \frac{9!}{2!7!} \cdot \frac{7!}{3!4!} = \frac{9!}{2!3!4!}$$ ways, in agreement with above.
Notice that labeling the team with four students team A, the team with three students team B, and the team with two students team C would not change our answer.
More care would be required if two or more of the groups had the same size.
Suppose our students are Amanda, Brenda, Claire, Dennis, Edward, Fiona, Gloria, Henry, and Ivan.
If we divide the nine students into teams of three, then the $3! = 6$ divisions \begin{align*} & \{Amanda, Brenda, Claire\}, \{Dennis, Edward, Fiona\}, \{Gloria, Henry, Ivan\}\\ & \{Amanda, Brenda, Claire\}, \{Gloria, Henry, Ivan\}, \{Dennis, Edward, Fiona\}\\ & \{Dennis, Edward, Fiona\}, \{Amanda, Brenda, Claire\}, \{Gloria, Henry, Ivan\}\\ & \{Dennis, Edward, Fiona\}, \{Gloria, Henry, Ivan\}, \{Amanda, Brenda, Claire\}\\ & \{Gloria, Henry, Ivan\}, \{Amanda, Brenda, Claire\}, \{Dennis, Edward, Fiona\}\\ & \{Gloria, Henry, Ivan\}, \{Dennis, Edward, Fiona\}, \{Amanda, Brenda, Claire\} \end{align*} are all equivalent since they result in the same three teams. Therefore, the number of ways of dividing the class into three unlabeled teams of three is $$\frac{1}{3!}\binom{9}{3}\binom{6}{3} = \frac{1}{3!} \cdot \frac{9!}{3!3!3!}$$ We divide by $3!$ to account for the $3!$ orders in which we could select the same three teams of three.
Similarly, if the teams are not labeled and we divide the class into two teams of two and one team of five, the two divisions \begin{align*} \{Amanda, Brenda\}, \{Claire, Dennis\}, \{Edward, Fiona, George, Henry, Ivan\}\\ \{Claire, Dennis\}, \{Amanda, Brenda\}, \{Edward, Fiona, George, Henry, Ivan\} \end{align*} are equivalent since they result in the same three teams. Hence, the number of ways of dividing the nine students into two teams of two and one team of five if the teams are unlabeled is $$\frac{1}{2!}\binom{9}{2}\binom{7}{2} = \frac{1}{2!} \cdot \frac{9!}{2!2!5!}$$ We divide by $2!$ to account for the $2!$ orders in which we could pick the same teams of size two.
If we had instead picked the team of five first, we would be left with four people. You might think that the two teams of two could be picked in $\binom{4}{2}$ ways, but this counts every team twice, once when we choose a team and once when we choose its complement. Alternatively, notice that if our team of five consists of Edward, Fiona, Gloria, Henry, and Ivan, the two teams of two are distinguished by who is paired with Amanda. There are three ways to do this: \begin{align*} \{Amanda, Brenda\}, \{Claire, Dennis\}\\ \{Amanda, Claire\}, \{Brenda, Dennis\}\\ \{Amanda, Dennis\}, \{Brenda, Claire\} \end{align*} Hence, the number of divisions of nine students into two teams of two and one team of five is $$\binom{9}{5} \cdot 3 = \binom{9}{5} \cdot \frac{1}{2}\binom{4}{2} = \frac{1}{2}\binom{9}{5}\binom{4}{2} = \frac{1}{2!} \cdot \frac{9!}{2!2!5!}$$
Notice that the team of five is distinguished by its size, while the two teams of two are not. The teams of two can only be distinguished by who is on which team.
To summarize, teams of different sizes are distinguished by their sizes, so the order in which they are selected does not matter. If we have unlabeled teams of the same size, we have to divide by the number of orders in which we could pick the same teams.