# Difference between 2 solutions, one is correct and the other is wrong, in a permutation problem

The question is: From 4 oranges, 3 bananas and 2 apples, how many selections of 5 pieces of fruit can be made, taking at least 1 of each kind?

My attempt at this is as follow:

1. Choose 1 orange from 4:$$\binom{4}{1}$$ = 4 ways.
2. Choose 1 banana from 3:$$\binom{3}{1}$$ = 3 ways.
3. Choose 1 apple from 2: $$\binom{2}{1}$$ = 2 ways.
4. Choose 2 fruits from the remaining (3 oranges, 2 bananas, 1 apple): $$\binom{6}{2}$$ = 15

Multiplying these together: $$4 \times 3 \times 2 \times 15 = 360$$ which is incorrect because this exceed the total number of selections of any 5 fruits without any restriction: $$\binom{9}{5}$$.

However, other solutions that I have found either:

1. Add up different combinations of the fruit: Is there a shortcut to this combination problem?
2. Take the total number of selections, then subtract each selection that fails to have at least one of a kind.

Both of these solutions lead to 98. I understand the 2 correct solutions but I am being torn up not being able to find out the flaw of my own attempt at the solution. Can someone please point out the difference in my incorrect solution and the correct ones? Why is it wrong? Thank you so much in advance.

• The total number of selections without any restriction equals $\frac{9!}{4!3!2!}$, which is $1260$, not $126$ ($\binom{9}{5}$). Jan 22 at 9:38
• Are fruit of the same type distinguishable? In other words: Is it the same if you take orange number 1 or orange number 2? Jan 22 at 10:04
• @Dominique give it another try. $\left( ^9 _5\right)$ = $126$, not $1260$ Jan 22 at 10:24

Your answer ($$360$$) is incorrect because of double counting.

Let's say the four oranges are labeled $$O_1$$, $$O_2$$, $$O_3$$, and $$O_4$$.

Now let's consider two possibilities following the steps you included.

1. We choose $$O_2$$ in the first step and $$O_4$$ in the last step.

2. We choose $$O_4$$ in the first step and $$O_2$$ in the last step.

Assuming everything else is the same in the two cases, we end up with exactly the same fruits. But it is being counted twice.

In certain cases, the same outcome might get counted more than twice. That's why, your answer is way higher than the correct one.

In your incorrect solution you're multiply counting all of the ways of selecting the $$5$$ pieces of fruit. To illustrate, suppose each of the pieces of fruit is numbered as follows: $$\begin{array}{|c|c|c|c|} \hline \text{fruit}&\text{orange}&\text{banana}&\text{apple}\\ \hline \text{numbers}&1{-}4&5{-}7&8,9\\ \hline \end{array}$$ Now if you list the ways of choosing the $$5$$ pieces of fruit by your method of counting, in numerical order with oranges counting as most significant to apples as least significant, the first three selections of them will be: \begin{align} \text{first selection:}&1,5,8,9,6\\ \text{second selection:}&1,5,8,9,7\\ \text{third selection:}&1,6,8,9,5\ . \end{align} Notice that the set of pieces of fruit you have in the third selection is the same as that you have in the first selection, so these are really the same way of choosing the $$5$$ pieces of fruit, but your method of counting counts them as two different ways.

Firstly, why have you changed a combination problem into a permutation problem in your header ?

Secondly, in the original question it has implicitly been assumed that each fruit is distinguishable If fruits of the same kind are indistinguishable, the answer would be just $$5$$: in the order orange,banana, apple,
$$3-1-1,\;\;2-2-1,\;\;2-1-2,\;\;1-3-1,\;\;1-2-2$$

The answer of 98 implicitly assumes that fruits of the same kind are distinguishable. Taking that to be so,

whenever you fractionate the selection process of distinguishable objects, you tend to over count as shown by lonza leggiera

As for a shortcut for the selection, two methods hav already been given, here is a third.

Denoting the number of fruits selected by the coefficient of $$x$$, oranges selected may be $$x,x^2,x^3$$ and $$x^4$$, and similarly for other types of fruits.

And since multiplyimg polynomials adds up coefficients, the answer can be found as the coefficient of $$x^5$$ in

$$\left[\binom41x+\binom42x^2+\binom43x^3+\binom44x^4\right]\left[\binom31x+\binom32x^2+\binom33x^3\right]\left[\binom21x+\binom22x^2\right]$$

yielding the answer = $$98$$