0
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ "Every student should take exactly one copy of some discrete mathematics book. " This line seems ambiguous $\endgroup$
    – UmbQbify
    Jun 18, 2020 at 9:38
  • $\begingroup$ i am not a native english speaker , I am trying to say that every student takes exaclty one book, not one from every category but one in total $\endgroup$ Jun 18, 2020 at 10:37

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ i am trying to get what you are saying.. do you mean that for example i can choose students A,B,C,D and give them let's say books 1 , 2 , 3, 4 accordingly. Let's not this disturbution as : (A,B,C,D) = ( 1, 2, 3, 4, ) . Now let's say i am picking students : A, B, C and E and we have this disturbution : (A,B,C,E)=(1,2,3,4) . In both cases (A,B,C) = (1,2,3) . Do you mean that I am overcounting that? $\endgroup$ Jun 18, 2020 at 10:42
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ you mean that my solution counts : (1 ,2, 3, 4) = (H,R,L,E) and then (5) = (R) , as different from (1,3,4,5) = (H,L,E,R) and then (2)=R , if I am getting this right? amazing how wrong I was.. $\endgroup$ Jun 18, 2020 at 10:52
  • $\begingroup$ Yes, that was what the issue was. $\endgroup$ Jun 18, 2020 at 12:56

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.