4
$\begingroup$

We have 4 bananas, 5 apples, 6 oranges. How many ways can we choose 7 fruits with at least 4 oranges? The straight forward method is to divide this into cases with 4, 5, or 6 oranges and then picking from bananas and apples, so that we have chosen 7 fruits. If we compute each case and add them up, we get: $$\binom 64\binom 93+\binom 65\binom 92+\binom 66\binom 91=1485$$ But there is a simpler way; first pick 4 oranges from those 6 oranges (so that we have picked at least 4 oranges), and then choose 3 fruits from the remaining fruits (2 oranges, 5 apples and 4 bananas which sum to 11 fruits). This way we do have picked 7 fruits and at least 4 of them are oranges but the result is: $$\binom 64\binom {11}3=2475$$ which is different from the actual answer. How can I rigorously check which method works without having to list all the combinations?

$\endgroup$
  • 1
    $\begingroup$ I am using the rule of sum and rule of product. The binomial coefficients represent the number of combinations. I want know what went wrong that I got two different answers from two different but seemingly logical and correct methods of counting. How can I avoid such counting errors by rigorously proving the right method without having to list all of the combinations? I don't know much beyond the rules I stated, so please consider that while answering. $\endgroup$ – M.Mahdi Aug 3 at 1:15
4
$\begingroup$

Your second method counts each selection that has $5$ oranges $\binom54=5$ times, and each selection that has $6$ oranges $\binom64=15$ times. In each case you count the selection once for each set of $4$ oranges contained in it: any one of those sets could be the set of $4$ that you preselected.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ So, I just counted the same objects more than once? But, the method's logic seems correct. What is the right way of applying the logic if the second method I mentioned, is not? And how to deduce that the method is counting things correctly? In this problem, the correct answer was given by the first method, so the second method has indeed counted some objects more than once. But in an exam situation, I can't try both methods. $\endgroup$ – M.Mahdi Aug 3 at 1:28
  • $\begingroup$ @M.Mahdi: In general you need to ask yourself whether a method of counting could possibly count the same collection or arrangement of things more than once. Notice that your second approach singles out $4$ oranges for special treatment. This means that whenever we end up choosing more than $4$ oranges, we’re actually counting our oranges in two groups, the original $4$ and the one or two that we added later. But we can get the same $5$ or $6$ oranges with a different division of them into original $4$ and extras, and each of those divisions gets counted separately. This is something to ... $\endgroup$ – Brian M. Scott Aug 3 at 1:56
  • $\begingroup$ ... watch for whenever you single out a specific subset of some collection whose elements should be treated identically. In this case we’re singling out $4$ oranges as the ones originally chosen, distinguishing them from any that we choose later, even though all that we care about is which oranges were selected. $\endgroup$ – Brian M. Scott Aug 3 at 1:59
  • $\begingroup$ Thanks. This works. $\endgroup$ – M.Mahdi Aug 3 at 2:22
  • $\begingroup$ @M.Mahdi: You’re welcome. $\endgroup$ – Brian M. Scott Aug 3 at 2:33

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.