4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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}. $$

$\endgroup$
2
  • $\begingroup$ thanks for your answer, but you are writing, using summation, the same as I did. I was expecting a different approach. $\endgroup$ – David Robert Jones Jul 6 '13 at 3:04
  • $\begingroup$ I can certainly understand that. However, I don't think that you'll find an identity/combinatorial idea that simplifies this, except in the special case (which you've already addressed) that you're allowed to choose as many of each flavor as you like. $\endgroup$ – Nick Peterson Jul 6 '13 at 3:14

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.