6.042/18.062J Mathematics for Computer Science - Recitation 15

Question

I have a question on the following problem:

3. An independent living group is hosting eight pre-frosh, affectionately known as P1 , . . . , P8 by the permanent residents. Each pre-frosh is assigned a task: 2 must wash pots, 2 must clean the kitchen, 1 must clean the bathrooms, 1 must clean the common area, and 2 must serve dinner. In how many ways can P1 , . . . , P8 be put to productive use?

Solution:

There is a bijection from sequences containing two P ’s, two K’s, a B, a C, and two D’s. In particular, the sequence (t1 , . . . , t8 ) corresponds to assigning Pi to washing pots if ti = P , to cleaning the kitchen if ti = K, to cleaning the bathrooms if ti = B, etc. Therefore, the number of possible assignments is: $8! / (2!.2!.1!.1!.2!)$

I understand the solution but why we didn't divide the answer by $5!$, that is, the number of ways to choose the order of groups, for example we could choose the groups in the reverse order: 2 must serve dinner, 1 must clean the common area, 1 must clean the bathrooms, 2 must clean the kitchen and 2 must wash pots.

In the solution $8! / (2!.2!.1!.1!.2!)$ We considered the order by which we choose the 5 groups, and that is the definition of the multinomial coeffecient, but I think that this order doesn't matter in this problem.

I appreciate any help.

Answer 1

Why not divide by $5!$? The tasks are not interchangeable.

If we just wanted to divide the 8 people into 4 groups of 2... Then our formula would be $\frac {8!}{2!2!2!2!4!}$

But, if the task is to divide them into groups where each group has a defined character, that is a different question. We remove that $4!$ factor from the denominator.

You could think about it as we need 2 people to do task A. That splits our group into those 2 and the 6 assigned to other tasks. Then we assign 2 from the 6 to task B, leaving 4 for other tasks. Putting the sequence together gives.

${8\choose 2}{6\choose 2}{4\choose 1}{3 \choose 1}{2\choose 2}$

Next replace ${a\choose b}$ with $\frac {a!}{b!(a-b)!}$ in each above.

$\left(\frac {8!}{2!6!}\right)\left(\frac{6!}{2!4!}\right)\left(\frac {4!}{1!3!}\right)\left(\frac {3!}{1!2!}\right)\left(\frac {2!}{2!0!}\right)$

Multiply and simplify:

$\frac {8!}{2!2!1!1!2!}$

Answer 2

The multinomial coefficient $$\binom{8}{2, 2, 1, 1, 2} = \frac{8!}{2!2!1!1!2!}$$ is an efficient way of representing the following scenario:

Choose two of the eight pre-frosh to wash pots, which can be done in $\binom{8}{2}$ ways; two of the remaining six pre-frosh to clean the kitchen, which can be done in $\binom{6}{2}$ ways; one of the remaining four pre-frosh to clean the bathrooms, which can be done in $\binom{4}{1}$ ways; one of the remaining three pre-frosh to clean the common area, which can be done in $\binom{3}{1}$ ways; and assign both of the remaining pre-frosh to serve dinner, which can be done in one way. Hence, there are $$\binom{8}{2}\binom{6}{2}\binom{4}{1}\binom{3}{1} = \frac{8!}{2!6!} \cdot \frac{6!}{2!4!} \cdot \frac{4}{1!3!} \cdot \frac{3!}{1!2!} = \frac{8!}{2!2!1!1!2!}$$ ways to assign work to the eight pre-frosh.

It does not make sense to divide by $5!$ since the groups are not the same size, nor does it make sense to divide by the $3!$ ways of assigning groups of $2$ and the $2!$ ways of assigning groups of $1$ since having, for instance, Amelia clean the common area and Benjamin clean the bathroom is a different assignment than having Amelia clean the bathroom and Benjamin clean the common area.