# How to approach this combinatorics problem?

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?

• Does order matter? – vrugtehagel May 12 '17 at 21:32
• @vrugtehagel No. – LearningMath May 12 '17 at 21:33
• 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? – Barry Cipra May 12 '17 at 21:39

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

• Can you please elaborate where you got this from? Thanks. – LearningMath May 12 '17 at 21:31
• $(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. – vadim123 May 12 '17 at 21:32
• Can you provide a reference for this approach? Thank you. – LearningMath May 12 '17 at 21:52
• See the second half of this. – vadim123 May 12 '17 at 23:32

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

• 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? – LearningMath May 12 '17 at 22:06

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

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

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