balls in bins

Balls in Bins PhL 3.5.03 1. In how many ways can you put 20 balls into 50 bins: (a) if they are non-identical; (b) if they are identical? (a) Take the first of the 20 balls, there are 50 ways to put it into the bin set. The same is true for the second ball. So the answer is 5020. In many of these "ways", some bins will have multiple balls. If the balls are 20 different colors, then if a bin ends up with exactly 3 balls red, green and blue, there is no overcounting going on. Exactly one of the 5020 ways will have this outcome in that specific bin. So I think the answer to the question of part (a) is indeed 5020. (b) If balls are all the same color and are indistinguishable in principle, then what? I am too stupid to know how to answer this question, so let's try a simpler problem. (N=2?) // OK, now I am less stupid, see below, and I see that the answer here is C(69,20). There are 51 bin walls, remove two so 49 internal bin walls, and 20 balls gives 69 symbols. We want to pick a committee of 20 of these 60 symbols to be asterisks. Or pick a committee of 49 symbols to be wall boundaries. This is the more logical way to say it I think. Each committee of 49 bin boundaries represents a unique partition of the set of balls. 2. How many ways can you put 2 balls into 3 bins: (a) if they are non-identical; (b) if they are identical? For (a) assume the balls are R and G color. Here are all the ways: 1 RG 2 R G 3 R G 4 G R 5 G R 6 RG 7 R G 8 G R 9 RG Sure enough, t here are 32 ways. Now if R=G, some of these ways are the same. For example, 2 and 4 are the same. Here are all the ways for identical, 1 GG 2 G G 3 G G 6 GG 7 G G 9 GG Now there are only 6 ways. How could I have computed this result ahead of time without listing them out in a dumbbell drawing? Web Help. Here is some interesting test related to this question: We start by finding the number of unrestricted ways that 20 balls can be distributed in 10 urns. We can illustrate the problem as follows: |****|***| |***|******| | ** | * | | * | This represents occupancy 4,3,0,3,6,0,2,1,0,1 The total number of possibilities is the same as the number of distinct arrangements of 20 *'s and 9 |'s. This is given by C(29,20) Very interesting indeed. I found finally a good little discussion of this kind of "occupancy problem", and the method above is in fact the standard way you do these things. In the above example, there are 10 urns, so there are really 11 boundaries so we start with 11 bars and 20 *. However, we only care about solutions that have a bar on each end. So remove those two bars, and then you end up with 9 bars and 20 urns, and that gives you the C(29,20). The ways to put 2 balls in 3 bins if balls are identical: imagine 2 balls and 2 bin boundaries so 4 objects to arrange. Answer is then (4,2) which is 4! / 2! 2! = 4*3*2 / 2*2 = 6, the result obtained above.