1
$\begingroup$

There are $5$ different apples, $4$ different oranges, and $3$ different bananas. Number of ways to select at least one of each kind?

My first approach: I selected one of each kind first and then I have $9$ fruits remaining, of which I can choose in $2$ ways [either include or exclude].

$${5\choose1} \cdot {4\choose1} \cdot {3\choose1} \cdot (2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2)$$

My second approach: $$\bigg({5\choose1}+{5\choose2}+{5\choose3}+{5\choose4}+{5\choose5}\biggl)\bigg({4\choose1}+{4\choose2}+{4\choose3}+{4\choose4}\bigg)\bigg({3\choose1}+{3\choose2}+{3\choose3}\bigg)$$

but the two methods give different answers.

I know my second approach is correct, but what is going wrong in my first approach?

You can help me by giving small example.

$\endgroup$
2
  • $\begingroup$ Welcome to MathSE. This tutorial explains how to typeset mathematics on this site. $\endgroup$ Dec 5, 2020 at 11:15
  • $\begingroup$ It would improve your Question to show the "different answers." Sometimes math gives two different expressions that agree in value. Presumably you checked and one of these gives a bigger value than the other, which is a clue about what when wrong (one of the methods double counts some outcomes). $\endgroup$
    – hardmath
    Dec 5, 2020 at 15:03

1 Answer 1

2
$\begingroup$

There are a total of $5 + 4 + 3 = 12$ fruits. You can either select or not select each fruit. Thus, if we did not have the restriction that at least one fruit of each type must be selected, there would be $2^{12} = 4096$ possible ways to select the fruits (including the choice of not selecting any of them). Your first approach gives $$\binom{5}{1}\binom{4}{1}\binom{3}{1} \cdot 2^9 = 30,720$$ an indication you are over counting.

Let's focus on the apples. According to the count in your first approach, there are $$\binom{5}{1} \cdot 2^4 = 80$$ ways to select at least one apple rather than $$\binom{5}{1} + \binom{5}{2} + \binom{5}{3} + \binom{5}{4} + \binom{5}{5} = 31$$ ways to select at least one apple. This is because you count each selection with exactly $k$ apples $k$ times, once for each way you could have designated one of those $k$ apples as the apple you selected. To illustrate this, consider the following two examples.

Suppose the five apples are Ambrosia, Fuji, Gala, Granny Smith, and Honeycrisp. You count the selection of an Ambrosia apple and a Fuji apple twice, depending on which of those apples you designate as the apple you have selected.

$$ \begin{array}{l l} \text{apple} & \text{additional apples}\\ \hline \text{Ambrosia} & \text{Fuji}\\ \text{Fuji} & \text{Ambrosia} \end{array} $$

You count the selection of an Ambrosia apple, a Fuji apple, and a Gala apple three times, depending on which of those apples you designate as the apple you have selected.

$$ \begin{array}{l l} \text{apple} & \text{additional apples}\\ \hline \text{Ambrosia} & \text{Fuji, Gala}\\ \text{Fuji} & \text{Ambrosia, Gala}\\ \text{Gala} & \text{Ambrosia, Fuji} \end{array} $$

Since your first approach counts each selection of exactly $k$ apples $k$ times, your first approach yields $$1 \cdot \binom{5}{1} + \color{red}{2} \cdot \binom{5}{2} + \color{red}{3} \cdot \binom{5}{3} + \color{red}{4} \cdot \binom{5}{4} + \color{red}{5} \cdot \binom{5}{5} = \color{red}{5 \cdot 2^4} = \color{red}{80}$$ ways to select at least one apple, $$1 \cdot \binom{4}{1} + \color{red}{2} \cdot \binom{4}{2} + \color{red}{3} \cdot \binom{4}{3} + \color{red}{4} \cdot \binom{4}{4} = \color{red}{4 \cdot 2^3} = \color{red}{32}$$ ways to pick at least one orange, and $$1 \cdot \binom{3}{1} + \color{red}{2} \cdot \binom{3}{2} + \color{red}{3} \cdot \binom{3}{3} = \color{red}{3 \cdot 2^2} = \color{red}{12}$$ ways to pick at least one banana, giving your total of $$\color{red}{80 \cdot 32 \cdot 12} = \color{red}{30,720}$$ ways to select at least one fruit of each type.

A final note: There are $2^n$ subsets of a set with $n$ elements since we can either choose to include or not include each of the $n$ elements in a subset. Of these $2^n$ subsets, $2^n - 1$ are nonempty. Hence, there are $2^5 - 1$ ways to select at least one of the five apples, $2^4 - 1$ ways to select at least one of the four oranges, and $2^3 - 1$ ways to select at least one of the three bananas. Therefore, there are $$(2^5 - 1)(2^4 - 1)(2^3 - 1) = 31 \cdot 15 \cdot 7 = 3255$$ ways to select at least one fruit of each type. Notice that $$\left[\binom{5}{1} + \binom{5}{2} + \binom{5}{3} + \binom{5}{4} + \binom{5}{5}\right]\left[\binom{4}{1} + \binom{4}{2} + \binom{4}{3} + \binom{4}{4}\right]\left[\binom{3}{1} + \binom{3}{2} + \binom{3}{3}\right] = 31 \cdot 15 \cdot 7 = 3255$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .