1
$\begingroup$

You have $12$ different flavors of ice-cream. You want to buy $5$ balls of ice-cream, but you want at least one to be made of chocolate and also you don't want more than $2$ balls per flavor. In how many ways can you can choose the $5$ balls?

$\endgroup$
  • $\begingroup$ Does order matter? $\endgroup$ – vrugtehagel May 12 '17 at 21:32
  • $\begingroup$ @vrugtehagel No. $\endgroup$ – LearningMath May 12 '17 at 21:33
  • $\begingroup$ Partial hint: If $2$ of the balls are chocolate, the other $3$ balls can be chosen in ${11\choose3}+11\cdot10$ ways. Do you see why? $\endgroup$ – Barry Cipra May 12 '17 at 21:39
2
$\begingroup$

Calculate the coefficient of $x^5$ in $$(x^1+x^2)(x^0+x^1+x^2)^{11}$$

$\endgroup$
  • $\begingroup$ Can you please elaborate where you got this from? Thanks. $\endgroup$ – LearningMath May 12 '17 at 21:31
  • $\begingroup$ $(x^1+x^2)$ chooses one or two chocolate balls. Each $(x^0+x^1+x^2)$ chooses zero, one, or two balls of that flavor. $\endgroup$ – vadim123 May 12 '17 at 21:32
  • $\begingroup$ Can you provide a reference for this approach? Thank you. $\endgroup$ – LearningMath May 12 '17 at 21:52
  • $\begingroup$ See the second half of this. $\endgroup$ – vadim123 May 12 '17 at 23:32
1
$\begingroup$

This is the same as no of solutions of $\sum_{i=1}^{12} x_i=5$ where $1≤x_1≤2$ and for the other $x_i$'s $0≤x_i≤2$ which is the same as coefficient of $x^5$ in $(x^1+x^2)(x^0+x^1+x^2)^{11}$

$\endgroup$
  • $\begingroup$ How is it the same as the coefficient of $x^5$ in $(x^1+x^2)(x^0+x^1+x^2)^{11}$ ? Can you provide a reference where I can read more about this? $\endgroup$ – LearningMath May 12 '17 at 22:06
1
$\begingroup$

Decide if chocolate will be a double ($c=1$) or a single ($c=0$).

If $c=0$, take a chocolate ball. Decide how many "doubles" $d\in\{0,1,2\}$ you want and make one of $11 \choose d$ specific choices regarding which non-chocolate flavors you want. These $d$ colors and chocolate are now off limits, so choose $5-1-2d=4-2d$ colors from each of the remaining $12-d-1=11-d$ legal options.

If $c=1$, take two chocolate balls. Decide how many "non-chocolate doubles" $d\in\{0,1\}$ you want and make one of $11 \choose d$ choices regarding the non-chocolate flavors. These $d$ colors and chocolate are now off limits, so choose $5-2-2d=3-2d$ flavors from each of the remaining $12-d-1=11-d$ legal options.

$$\sum_{d=0,1,2} {11 \choose d}{{11-d} \choose {4-2d}} + \sum_{d=0,1} {11 \choose d}{{11-d} \choose {3-2d}}$$

$$= {11 \choose 2} + \sum_{d=0,1} {11 \choose d} \left[{{11-d} \choose {4-2d}} + {{11-d} \choose {3-2d}}\right]$$

which is $55 + [1*495 + 11*55]=1155$.

$\endgroup$
0
$\begingroup$

You can also answer this using careful counting Case by case basis splitting into exactly two pairs of flavors, one pair of flavors and no pairs.

$$C_1,P_1,P_1,P_2,P_2 = 1*12*11$$ $$C_1,P_1,P_1,P_2,P_3=1*12*11*10/2!$$ $$C_1,P_1,P_2,P_3,P_4=1*12*11*10*9/4!$$

How many of these ways lead to more than $2$ chocolates?

If $$P_1=C$$ which for the first case can happen $11$ ways, the second case can happen $11*10/2!$ ways and the last case can't happen if just $P_1=C$

What about if $P_2=C$ the first case can happen in $11$ ways and the second case can happen in 11*10/2! ways.

If $P_3,P_4=C$ then we don't get $3$ or more chocolates, so we are done! The final answer is $$12*11+12*11*10/2! +12*11*10*9/4!-11*10/2!-11-11-11*10/2!=1155$$

$\endgroup$
0
$\begingroup$

I think the most obvious/straightforward way to solve this is to use combination 'with repetition'/'stars and bars' and then subtract all inapplicable cases. (https://en.wikipedia.org/wiki/Combination#Number_of_combinations_with_repetition). $\space$The formula for this for selecting $r$ from $n$ is ${{n+r-1}\choose r}$. $\space$(I like to think of this as selecting $r$ 'items' from the $n+r-1$ 'walls' and 'items' and then letting the $n-1$ 'walls' 'fall into place.')

Dividing into cases where there is one chocolate ball and more than one.

One chocolate ball of ice cream:

$11$ flavors left to choose from. Is combination 'with repetition' with $n=11$ and $r=4$ and then subtract all inapplicable cases. (All cases - cases where there are $3$ of $1$ flavor and $1$ of another - cases where there are $4$ of one flavor):

${{11+4-1=14}\choose 4}-{11\choose 1}{10\choose 1}-{11\choose 1}=1001-110-11=880$

Two chocolate balls of ice cream:

$11$ flavors left to choose from. Is combination 'with repetition' with $n=11$ and $r=3$ and then subtract all inapplicable cases. (All cases - cases where there are $3$ of $1$ flavor):

${{11+3-1=13}\choose 3}-{11\choose 1}=286-11=275$

For a grand total of $1155$.

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