A certain ice cream store has 31 flavors of ice cream available. In how many ways can we…

Question

A certain ice cream store has 31 flavors of ice cream available. In how many ways can we order a dozen ice cream cones if chocolate, one of the 31 flavors, may be ordered no more than 6 times?

$\dbinom{31 + 12 - 1}{12}$ would be the total number of cases if not for the restriction of chocolate no more than 6 times. To fix this we could substract the invalid cases:

• Exactly 7 chocolate cones ordered: $\dbinom{30 + 5 - 1}{5}$ -> 30 because chocolate is not an option anymore, 5 because we still have to fill 5 cones to have the dozen.
• Exactly 8 chocolate cones ordered: $\dbinom{30 + 4 - 1}{4}$
• .
• .
• .
• Exactly 12 chocolate cones ordered: $\dbinom{30 + 0 - 1}{0}$

Solution:

$\dbinom{31 + 12 - 1}{12} - ( \dbinom{30 + 5 - 1}{5} + \dbinom{30 + 4 - 1}{4} + \dbinom{30 + 3 - 1}{3} + \dbinom{30 + 2 - 1}{2} + \dbinom{30 + 1 - 1}{1} + \dbinom{30 + 0 - 1}{0} )$

Is the reasoning correct? If so, can we avoid the invalid cases sum? This could complicate; suppose 155 flavors and a restriction of no more than 30 times.

Thanks.

Answer 1

You can get rid of the cases. As you say, there are $\binom{12+31-1}{31-1}=\binom{42}{30}=\binom{42}{12}$ ways without the restriction. To count the unacceptable ways, note that each ‘bad’ way has at least seven chocolate cones, so that you’re really just counting the number of ways to order ($7$ chocolate cones and) another $5$ cones with no restrictions. That’s just the number of ways to order $5$ cones without restriction, which is $\binom{5+31-1}{31-1}=\binom{35}{30}=\binom{35}5$, so the total number of acceptable orders is

$$\binom{42}{12}-\binom{35}5=11,058,116,888-324,632=11,057,792,256\;.$$

As a check, note that by a standard binomial identity we have

$$\sum_{k=0}^5\binom{k+29}k=\sum_{k=0}^5\binom{k+29}{29}=\binom{5+29+1}{29+1}=\binom{35}{30}=\binom{30}5\;,$$

showing that this answer is the same as yours.

Answer 2

Your reasoning is sound. Here's another way you could look at it:

Suppose that we choose exactly $k$ that are chocolate. Then the remaining $12-k$ are chosen from anything other than chocolate; this can be done in $$ \binom{30+12-k-1}{12-k} $$ ways. So, then the answer we want is $$ \sum_{k=0}^{6}\binom{41-k}{12-k}. $$ (You can check, for instance in Mathematica, that this agrees with your answer above.)

If you wanted to expand to the case of 155 flavors and choosing chocolate no more than 30 times, you would get $$ \sum_{k=0}^{30}\binom{154+(30-k)-1}{30-k}. $$