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 {apple} or {orange}
     for i = 2; There are 3 ways {apple, apple} or {apple, orange} or {orange, 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?

  • 1
    $\begingroup$ Forget about the at least one condition temporarily. We can choose $0$ apples or $1$ or $2$ and so on up to $9$, a total of $10$ possibilities. For each of these, there are $7$ choices for the oranges, anything from $0$ to $6$, for a total of $70$. finally, subtract the $1$ forbidden case where you pick $0$ of each. $\endgroup$ – André Nicolas Sep 24 '14 at 22:56

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*7 = 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.

  • $\begingroup$ How would this expand then if they were distinguishable from each other? Say from 9 men and 6 women? Would it be like [(9 choose 0)*(6 choose 0)*(6 choose 1)*...*(6 choose 6)]*[(9 choose 1)*.. etc? $\endgroup$ – James Bender Sep 24 '14 at 23:14
  • $\begingroup$ Edited my answer. $\endgroup$ – August Sep 24 '14 at 23:27
  • $\begingroup$ Ah I see.. Cause the sum (n choose i) for all i<= n is 2^n.. It's like the size of the set of all subsets minus the null set? $\endgroup$ – James Bender Sep 24 '14 at 23:29

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.