I am wondering if someone can explain the reasoning behind the solution my book gives me to the following problem:
How many ways are there to pick some pieces of fruit from $9$ oranges and $6$ apples if at least 1 piece is picked? Assume that apples are indistinguishable from other apples and oranges are likewise indistinguishable. Order is also not important.
My reasoning was as follows:
${\sum_{i=1}^{15}}$ Number of ways to choose i fruits
So for $i = 1$; There are $2$ ways $\{\text{apple} \}$ or $\{\text{orange}\}$
for $i = 2$; There are $3$ ways $\{\text{apple}, \text{apple}\}$ or $\{\text{apple}, \text{orange}\}$ or $\{\text{orange}, \text{orange}\}$
and so on until $i = 15$, then they all add up to $69$ which is the right answer.
However, The book solution says:
Since $0$ is a possibility for oranges and for apples but not for both, we have $(9+1)(6+1)$ – $1$ ways.
Can anyone explain why the author multiplies $(9+1)$ and $(6+1)$? I understand why $1$ is subtracted because it's like all the ways you can pick fruit minus the ways that you didn't pick any fruit. But how does $(9+1)(6+1) $ equal all the ways you can possible pick fruit?
Best Answer
If you have $9$ apples, you can choose $0, 1, 2, 3, ... 9$ of them. So there are $10$ ways to choose. Similarly for oranges, you have up to $7$ ways to choose. By the fundamental counting principle, you have $10\times7 = 70$ possible ways of choosing fruits (or no fruit). There is only one way to choose no fruit so we subtract $1$.
If you've used generating functions, you could also see it but it would also be a hassle to expand.
Also, have you ever encountered a problem such as "How many divisors does x have? (x non-prime)" It is similar to that where you add $+1$ to each power of the prime factorization when multiplying them.
If each apple and each orange were distinguishable, there would again be only one way to choosing nothing.
If the $9$ apples were distinguishable and the $6$ oranges were distinguishable, I believe this is the same as considering $9 + 6 = 15$ different objects.
How many ways are there to choose from $15$ different objects? There are $2^{15}$ such ways (including not choosing anything). Then $2^{15}-1$ is gives you the number of ways in which you have to choose at least one fruit. This is analogous to a power set.