2
$\begingroup$

I was looking at this problem in my textbook where, it was asking in how many ways, one could choose from 31 ice cream flavors for 12 cones(each receiving one scoop), where a flavor may not be ordered more than 11 times. The answer to the question seems rather simple: ${n+r-1 \choose r} - 31 = {31+12-1 \choose 12} - 31$

So basically, all possible combination of flavors with repetition, minus the 31 ways of having 12 cones with the same flavor.

I was however wondering how would one approach this type of problem if for instance the same question was asked with the condition where a flavor was not allowed to be ordered more than 10 times or any other number less than 12. Is there a generalized way of approaching this?

$\endgroup$
1
$\begingroup$

It can get messy. Let us first solve the problem where no single flavour can be ordered more than $7$ times. This will turn out to be straightforward.

Count the number of unrestricted ways of choosing in the usual way. Now subtract the number of bad choices. A bad choice involves choosing a flavour more than $7$ times. Which flavour? That can be chosen in $31$ ways. Grab $8$ cones of that flavour. We need $4$ more cones, of any flavours. The number of ways to do this is easy to handle, ordinary Stars and Bars.

This procedure no longer works if, for example, we are getting $100$ cones, and the restriction is that we cannot have more than $40$ of any flavour. For then there are also bad choices where we have more than $40$ of two flavours. This is not too tough to handle. There are $\binom{31}{2}$ ways to choose the two flavours, and now we need $18$ more cones of any flavours.

However, things begin to get out of control if we are ordering $100$ cones and the restriction is no more than $12$ of any flavour. It is still in principle doable, but not computationally easy.

| cite | improve this answer | |
$\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.