0
$\begingroup$

I am trying to solve the following problem on combinations:

Ten people visit an ice-cream shop that sells the following ice-cream flavours: Apricot, Banana, Cherry, and Apple.

There are enough banana flavoured ice-cream for at most 5 people, and only enough cherry flavoured ice-cream for at most 3 people. How many different combinations of ten ice-creams can the group choose?

It seems apparent that I must use the formula $ C(n+r-1, r) $. It seems tedious to compute the answer as I have to compute the number of combinations for 0, 1 ... 5 banana flavoured ice-cream and do the same for cherry flavoured ice-cream. Hence, I am not sure how to solve the question. Could anyone suggest an elegant solution for this?

$\endgroup$
1
$\begingroup$

Let $x_1$ denote the number of people who choose apricot, $x_2$ denote the number of people who choose banana, $x_3$ denote the number of people who choose cherry, and $x_4$ denote the number of people who choose apple. Then we wish to determine the number of solutions of the equation $$x_1 + x_2 + x_3 + x_4 = 10 \tag{1}$$ subject to the restrictions that $x_2 \leq 5$ and that $x_3 \leq 3$. If there were no such restrictions, the formula you cited tells us that the number of ways the ten people could choose the flavors would be $$\binom{10 + 3}{3} = \binom{13}{3}$$ However, we must exclude those selections in which $x_2 > 5$ or $x_3 > 3$.

Suppose that $x_2 > 5$. Then $x_2 \geq 6$, so $y_2 = x_2 - 6$ is a nonnegative integer. Substituting $y_2 + 6$ for $x_2$ in equation 1 yields \begin{align*} x_1 + y_2 + 6 + x_3 + x_4 & = 10\\ x_1 + y_2 + x_3 + x_4 & = 4 \end{align*} which is an equation in the nonnegative integers with $$\binom{4 + 3}{3} = \binom{7}{3}$$ solutions.

Suppose that $x_3 > 3$. Then $x_3 \geq 4$, so $y_3 = x_3 - 4$ is a nonnegative integer. Substituting $y_3 + 4$ for $x_4$ in equation 1 yields \begin{align*} x_1 + x_2 + y_3 + 4 + x_4 & = 10\\ x_1 + x_2 + y_3 + x_4 & = 6 \end{align*} which is an equation in the nonnegative integers with $$\binom{6 + 3}{3} = \binom{9}{3}$$ solutions.

If we subtract the number of selections in which one of the restrictions is violated from the total number of selections, we will have subtracted the selections in which both restrictions are violated twice. There is only one such selection, namely the one in which six banana and four cherry are selected. By the Inclusion-Exclusion Principle, the number of ways the flavors can be selected is $$\binom{13}{3} - \binom{7}{3} - \binom{9}{3} + \binom{3}{3}$$

$\endgroup$
0
$\begingroup$

So we have $i\leq 5$ people choosing banana and $j\leq 3$ choosing cherry. There are then $n=10-i-j$ people left and they can pick either Apricot or Apple. The different amount of combinations to do that are $n+1$ (simply counting how many people have chosen Apricot). So the solution would be

$$\sum_{i=0}^5\sum_{j=0}^3 10-i-j+1$$

This can easily be written out further.

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