# Thread: number of ways to...

1. ## number of ways to...

Friend hit me with this problem today.

There are three children with 20 fruit (10 peaches, 4 apples, and 6 pineapples).

How many ways can the fruit be passed out so a child has at least one of any kind of fruit?

My approach (which is wrong) is:

nCr(9,7)*nCr(6,4)*nCr(8,6) + nCr(12,10)*nCr(3,1)*nCr(8,6) + nCr(12,10)*nCr(6,4)*nCr(5,3)

(AKA, front load every kid 1 peach each, plus 1 apple each, plus 1 pineapple each)

This will count the number of ways each child is guaranteed one fruit. However it is over counting because when I front load 3 of any kind of fruit to a kid it is also re-counted in the other group when i front load another 3 fruit. Any advice how I can take out the over count?

PS: How do I use the awesome text so I don't have to use nCr?

2. Originally Posted by sonictech
Friend hit me with this problem today.

There are three children with 20 fruit (10 peaches, 4 apples, and 6 pineapples).

How many ways can the fruit be passed out so a child has at least one of any kind of fruit?
OK, so there are 3 kids, and we want to distribute 10 peaches, 4 apples and 6 pineapples among them so that each one of them has at least one of every kind of fruit.
As you correctly said, we can immediately give 1 peach, 1 apple and 1 pineapple to each of the 3 kids, and now we have 7 peaches, 1 apple and 3 pineapples.

We can distribute the remaining apple in 3 ways: give it to the first kid, to the second or to the third one.

In how many ways can we distribute $r$ indistinguishable pieces of fruit to $n$ kids, which are of course distinguishable? It can be shown that we can do it in $\binom{n+r-1}{r}$ ways.

So, we can distribute 7 remaining peaches to 3 kids in $\binom{3+7-1}{7}=\binom{9}{7}$ ways, and we can distribute 3 remaining peaches to 3 kids in $\binom{3+3-1}{3}=\binom{5}{3}$ ways.

To find the total number of possible distributions, we multiply the above numbers to get that the final answer is $3 \cdot \binom{9}{7} \cdot \binom{5}{3}$.

3. Originally Posted by sonictech
There are three children with 20 fruit (10 peaches, 4 apples, and 6 pineapples). How many ways can the fruit be passed out so a child has at least one of any kind of fruit?
I do not agree with the posted solution. That solution solves the question assuming that each child gets at least one of each kind of fruit. But the question is about each child getting at least one of any kind of fruit.

Without any restrictions, there are ${{10+3-1}\choose {10}}{{4+3-1}\choose {4}} {{6+3-1}\choose {6}}$ ways to give out the fruit.

There are ${{10+2-1}\choose {10}}{{4+2-1}\choose {4}} {{6+2-1}\choose {6}}$ ways to give out the fruit where child A gets no fruit whatsoever. Multiply by three to account for all three children.

But now we have counted three cases twice: cases in which one child gets all the fruit.

${{10+3-1}\choose {10}}{{4+3-1}\choose {4}} {{6+3-1}\choose {6}} - 3{{10+2-1}\choose {10}}{{4+2-1}\choose {4}} {{6+2-1}\choose {6}} + 3$.