we have 1000 copies of Hunter's, Rosen's, Liu's and Epp's discrete mathematics books and 1000 students .

Question

We have 1000 copies of Hunter's,1000 copies of Rosen's, 1000 of Liu's and 1000 copies of Epp's discrete mathematics books and 1000 distinct students . Every student should take exactly one copy of some discrete mathematics book. If there should be distributed at least one copy of every book , in how many ways can this be done?

My teacher's answer uses the "Inclusion-Exclusion" principle. We can violate the constraint if only one category is not distributed at all by $C(4,1)*3^{1000}$ ways, or if 2 categories are not distributed at all by $C(4,2)*2^{1000}$ or if 3 are not distributed at all by $C(4,3)*1^{1000}$ ways . In total : $4^{1000}-C(4,1)*3^{1000} + C(4,2)*2^{1000} - C(4,3)*1^{1000}$

My solution was this : We firstly need to make sure that at least 1 copy of every category is distributed so we pick 4 students with $C(1000,4)$ ways and we can give them book's with $C(1000,4)*4!$ ways . Then we are left of with 996 students. Those 996, can pick a book with $4^{996}$ ways . In total : $C(1000,4)*4!*4^{996}$ . Can you help me find my bug ? #update # my initial solution is totally wrong , amazing feedback follows. Εxtra question : Any tips to realise this needs Inclusion - Exclusion proinciple?

Answer 1

You are considering all the different ways 4 people can be chosen and distributing 4 of the books to them and randomly assigning other books to the others. the problem is that you are counting one case multiple times in different calculations.

Assume in scenario P: In your initial choice of 4 people, you choose people 1, 2, 3, and 4 and assign them books A, B, C, and D respectively in one of your calculations. now you assign book A to person number 5, B to 6, C to 7, D to 8, then again A to 9, and so on.

Now in scenario Q: In your initial choice of 4 people, you choose people 5, 6, 7, and 8 and assign them books A, B, C, and D respectively in one of your calculations. now you assign book A to person number 1, B to 2, C to 3, D to 4, then again A to 9, and so on.

You are counting cases P and Q (and actually many other cases that are the same) repeatedly while they represent the same assignment of books.

This is why using the inclusion-exclusion principle is the best way to solve this kind of problem without getting confused. The inclusion-exclusion principle prevents you from calculating the same assignment in different parts of your calculation.

Answer 2

It helps to try out the strategy with a smaller number of students. With only five students you teacher's method gives $$ 4^5-\binom{4}{1}\cdot3^5+\binom{4}{2}\cdot2^5-\binom{4}{3}\cdot1^5=1024-972+192-4=240 $$ ways. You can check that this is right by observing that some book must be distributed to two students and each of the other books to only one. There are four choices for which book goes to two students, and $\binom{5}{2}$ choices of the two students, and $3!$ ways to distribute the other three books to the remaining students: $4\cdot10\cdot6=240$.

Now try your method, which gives $$ \binom{5}{4}\cdot4!\cdot4^1=480 $$ ways. Why is your number too big? It's because distributing different books to students $1$, $2$, $3$, $4$ and any book to student $5$ includes some of the same configurations as distributing different books to students $1$, $3$, $4$, $5$ and any book to student $2$. For example, if students $1$, $2$, $3$, $4$ get $H$, $R$, $L$, $E$ in that order and student $5$ gets $R$, that's the same as students $1$, $3$, $4$, $5$ getting $H$, $L$, $E$, $R$ in that order and student $2$ getting $R$.

You can see why, in the case of five students, your method gives twice the correct count: each configuration has two descriptions, according to which of the two students who get the same book is included in the four who all get different books. So dividing your answer by $2$ gives the correct answer.

With more than five students, the overcounting factor in your method is not so predictable. In the case of six students, you can have three students all getting the same book and the other three each getting one of the remaining books, or two students both getting one book, two other students both getting some other book, and the other two each getting one of the two remaining books. The overcounting factor is different in these two cases: you're a factor of $3$ too high in the first case, but a factor of $4$ too high in the second. So the correct count is $1560$, of which $480$ are of the first type and $1080$ are of the second type. Your method gives an incorrect answer of $5760$, which breaks down as $$ 3\cdot480+4\cdot1080=5760. $$ You can see that it's going to become increasingly difficult to correct your method as the number of students grows.