in how many ways can 15 different balls can be distributed in 4 different boxes so that no box remain empty?

Question

answer is 4^15- 4C1.3^15+4C2.2^15-4C3.1^15
please explain the logic

Answer 1

Not a wordsmith, but I'll try.

There are 4^15 ways to put the balls in the boxes. We wish to remove the ways which leave at least one box empty.

There are 3^15 ways to put the balls into 3 boxes. We choose any one box of the four to exclude (leave empty). So, let's subtract 4C1 * 3^15.

Now, a problem- if we put the balls into just two boxes, we have subtracted them twice! (If they were in boxes 1 and 2, we subtracted them with boxes (1,2,3) and (1,2,4) from the three-box scenario.) So, we need to add them back into the fold. There are 2^15 ways to put the balls into only two boxes, and there are 4C2 ways to select the two boxes (to exclude or include). So, let's add 4C2 * 2^15 back.

Now, the distrubutions with all the balls in one box. When we subtracted the 3^15 * 4C1, these were subtracted three times (if they were in all in box one, with (1,2,3), (1,2,4) and (1,3,4)), and added three times ((1,2), (1,3), and (1,4)). That's a draw - which means we are still counting them. Thus we take them away, subtracting 4C3 * 1^15.

Total: 4^15- 4C1*3^15+4C2*2^15-4C3*1^15

This is the Principle of Inclusion/Exclusion.
Hope this helps.

Answer 2

morningfoxnorth, you're over counting.
For example, I could chose 4 different kinds of balls to put in each box as you did in the beginning. But I can still end up with the same balls in the same box in the end even if I chose another set of 4 different balls to begin with.

Answer 3

First put 1 ball in each box. There are 15x14x13x12 ways to do that = 32,760 ways.

That leaves 11 balls. They can be distributed in any way at all in the 4 boxes; there are 4^11 = 4,194,304 ways to do that.

32760 x 4,194,304 = 137,405,399,040 ways in all.

Answer 4

K-Dub has the correct approach and he should be given the 10 points. He beat me to it.

This problem is very similar to another one I answered some time back.
http://answers.yahoo.com/question/index;_ylt=ArrfyxDCCqXqNgB.r5duX.Lsy6IX;_ylv=3?qid=20071008141245AAIXE7L

In that problem you're trying to find the number of ways of rolling a k-sided dice n times, getting every digit at least once.
In this problem, you have 4 options and 15 trials, and you want to hit all 4 options at least once each.

The general answer is
k
∑ (-1)^i * (kCi) * (k-i)^n
i=0

Set k=4 and n=15 and you have your result.

Answer 5

while President Van Buren met the Prophet he asked Joseph Smith what the version became into between Mormonism and different religions of the day. The Prophet replied that the "mode of baptism, and the present of the Holy Ghost by potential of the laying on of arms" have been the undemanding transformations.