0
$\begingroup$

Assume that there are an arbitrarily large number of copies of ten different discrete math books (which we will call titles) for cmsc250. Each student must choose one title as the course text book. Assume that the five hundred students taking the course are indistiguishable.

How many different ways can the students choose titles, if Epp must be chosen by at most twenty students?

I understand that this is a stars and bars problem where the formula would be ${n+r-1}\choose{r-1}$, but whats throwing me off is the "at most" parameter of the problem. My answer is ${480+9-1}\choose{9-1}$ My reasoning was that we now have one less "bar", and that should be shown by lowering $r$ by 1

Am I approaching this the right way?

$\endgroup$
  • 1
    $\begingroup$ Flip the question around. Count the total allocations, and subtract off those that are at least 21. $\endgroup$ – Don Thousand May 2 at 22:53
1
$\begingroup$

We must subtract those cases in which at least $21$ students choose Epp's discrete mathematics book from the total.

If we let $x_i$, $1 \leq i \leq 10$, denote the number of textbooks of type $i$ that are chosen and $x_1$ denote the number of copies of Epp's textbook that are chosen, then we must find the number of solutions of the equation $$x_1 + x_2 + x_3 + x_4 + x_5 + x_6 + x_7 + x_8 + x_9 + x_{10} = 500 \tag{1}$$ in the nonnegative integers subject to the restriction that $x_1 \leq 20$.

A particular solution of equation 1 corresponds to the placement of $10 - 1 = 9$ addition signs in a row of $500$ ones. The number of such solutions is $$\binom{500 + 10 - 1}{10 - 1} = \binom{509}{9}$$ since we must choose which $9$ of the $509$ positions required for $500$ ones and $9$ addition signs will be filled with addition signs.

From these, we must subtract those solutions in which $x_1 > 20$.

Suppose $x_1 > 20$. Then $x_1' = x_1 - 21$ is a nonnegative integer. Substituting $x_1' + 21$ for $x_1$ in equation 1 and simplifying yields $$x_1' + x_2 + x_3 + x_4 + x_5 + x_6 + x_7 + x_8 + x_9 + x_{10} = 479 \tag{2}$$ Equation 2 is an equation in the nonnegative integers with $$\binom{479 + 10 - 1}{10 - 1} = \binom{488}{9}$$ solutions.

Hence, the number of ways the textbooks may be chosen if no more than $20$ copies of Epp's textbook are selected is $$\binom{509}{9} - \binom{488}{9}$$

$\endgroup$

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.