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.
Best Answer
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.