How many ways can we choose a team of $16$ people with $1$ leader and $4$ deputies out of $75$ people?

Question

How many ways can we choose a team of 16 people with 1 leader and 4 deputies out of 75 people?

I figured that we can select the 16 people out of the 75 simply with $75\choose 16$ but then should i continue multiplying with $16\choose 4$ and $12\choose 1$

Final : $75\choose 16$ * $16\choose 4$ * $12\choose 1$

Answer 1

There is more than way to enumerate the possibilities. For example, your way is to first identify the $16$ team members, then within those, identify the deputies and the leader. This yields two expressions, $$\binom{75}{16} \binom{16}{4} \binom{12}{1},$$ or you could do $$\binom{75}{16}\binom{16}{1}\binom{15}{4}.$$ These are equal.

Alternatively, you can reason as follows. Select the $1$ leader from the $75$ people; then select the $4$ deputies from the remaining $74$; then select the $11$ remaining members of the team to get $$\binom{75}{1}\binom{74}{4}\binom{70}{11}.$$

In fact, there are six different ways you can do this type of enumeration, depending on the order in which you select the regular team members, the deputies, and the leader. They are all equivalent. Why? Well, in the general, case, say with $n$ people, $t$ regular team members, $d$ deputies, and $r$ leaders, where $t+d+r \le n$ represents the total number of team members (regulars, deputies, and leaders), we have $$\binom{n}{t}\binom{n-t}{d}\binom{n-t-d}{r} = \frac{n!}{t! d! r! (n-(t+d+r))!}$$ and it becomes obvious that this expression is symmetric in $t, d, r$. The RHS expression is known as a multinomial coefficient and is sometimes written $$\binom{n}{t, d, r}.$$

Answer 2

Yes, the answer is correct.

The way to see that multiplying is correct, is that your previous choices don't influence the number of possible choices at a later step.

That is, pick your 16 people for the team, hence $\binom{75}{16}$. Regardless of what members of the team there are, you can always choose 4 of them in precisely $\binom{16}{4}$ ways to be deputies. The fact that the possible sets of deputies are different is irrelevant, only that their count stays the same.

You can confirm that $\binom{16}{4}\binom{12}{1}=\binom{16}{1}\binom{15}{4}$ results in the same number. Actually, even $\binom{16}{5}\binom{5}{1}$ will do. These other options correspond to "pick the leader first", and "pick 5 officers, 1 of whom will be the leader". These sorts of equivalences are the bread and butter of combinatorics.

Finally, all these products resolve to $\frac{16!}{11!\cdot4!\cdot1!}$, which looks like a natural extension of binomial coefficients, and is appropriately called the multinomial coefficient. You're splitting the team of 16 into three sets, of size 1, 4, 11.