# Basic Counting Problem

I was reading a probability book and am having trouble conceptually with one of the examples. The following is a modification. Let's say that we have $3$ coins that we want to randomly assign into $3$ bins, with equal probability. We can label these coins $a_1$, $a_2$, $a_3$. What is the probability that all $3$ bins will be filled? The solution is: All possible combinations of assigning these coins to bin locations is $3^3 = 27$. The possible ways that all 3 bins can be filled is $3!$. The final probability is $6/27 = 2/9$. Alternatively this could be derived as $(3/3)\cdot(2/3)\cdot(1/3) = 2/9$.

Now what if the coins are not labeled and are considered interchangeable. There are now $10$ configurations in which these bins can be filled: $\binom{3+3-1}{3} = 10$. Only one of these configurations will have all bins filled. Thus the probability here is $1/10$.

Shouldn't these probabilities be the same? Am I missing something with the second scenario?

-

When we select our sample space, it is very convenient for calculations if all elements of the sample space are equally likely. Then we can answer probability questions by counting.

In your proposed sample space of $10$ configurations, not all elements of the sample spave are equally likely. We can show this by a calculation. But one can also see that they need not be equally likely.

To simplify matters, imagine $2$ bins, and $20$ coins. It is intuitively almost obvious (and true) that a $20$-$0$ split is very much less likely than, say, a $10$-$10$ split, or a $11$-$9$ split. There are $21$ configurations ($0$ to $20$ cons in the first bin). These are not at all equally likely.

-
I was just writing a very similar answer, this is exactly the right way to look at it. I would just like to add that the probabilities depending on what you choose with equal probability. If you choose an arrangement with equal probability then the result is different for the two outcomes, but if you place the balls in bins sequentially, then the probability of the different arrangements happening is no longer uniform, and you get the same answer for both. (I think.) –  Tom Oldfield Nov 25 '12 at 0:46
@TomOldfield: Sequentially or not doesn't matter, as long as our placements are independent. So with our three coins and three bins, we grab a coin, oss a fair die. If get $1$ or $2$, first bin. If $3$ or $4$, second bin, and so on. For the second coin, repeat the tossing of the die. Then the sample space will be the $27$-member equally likely one. –  André Nicolas Nov 25 '12 at 0:50
Thank you for the answers. Does this mean that for finding the probabilities involving a set of interchangeable objects, we have to assume that each chosen object has a label anyways? The 2nd scenario is a variant of sampling with replacement and without ordering. Since the events in that scenario do not occur with equal likelihood, should this counting method never be used when computing probabilities? –  adam Nov 25 '12 at 0:52
Almost all the time, to get the right answer we need to assume the objects are distinct. There is an interesting case where this is not true, namely the "Bose-Einstein statistics." –  André Nicolas Nov 25 '12 at 0:56
@adam I tried to write a comment explaining why we normally use the method that we do, how to work out probabilities and some intuitive reasons for why we do it but it got too long, so I just added a new answer instead. It also explains why I used the word "sequentially", Andre. –  Tom Oldfield Nov 25 '12 at 13:14

Suppose that in the first case, you had a cat, a dog and a honey badger. You had 3 bins to put them in. The cat could go in any of the 3 boxes, so could the dog and so could the honey badger. You would have 27 possible combinations. Right?

Now, suppose you had 3 cats with no differences in them, then the configuration which was

(HB)(Cat)(Dog)
(Cat)(Dog)(HB)
(Cat),(HB),(Dog)


would be analogous to

(Cat)(Cat)(Cat)
(Cat)(Cat)(Cat)
(Cat)(Cat)(Cat)


in the second scenario and since there are no differences in the 3 cats, these configurations are exactly the same. Do you see why the difference exists between the 2 scenarios?

-
Semantically, I understand the difference. However it's intuitively confusing. For example, if all I care about is whether all three bins are filled, why does it matter if the coins are labeled or not? If I were to carry out this scenario in real life while blindfolded, shouldn't the likelihood of filling all three bins be the same in either scenario? –  adam Nov 25 '12 at 0:34
@adam. It depends on whether the coins are "distinguishable" or not. –  Inquest Nov 25 '12 at 6:19

The second way to model the problem loses the equally likehood of the event. For example, if you model the problem in the second way: Then there is only one way to fill each all the boxes, but in the way the experiment is done there are 6 ways. Also in the second way if you want to have the first box filled with 2 ball and the second with one you count it one time. But this can happen in the way of assingments in 3 ways. So you lose the symmetry of the problem.

-

It depends on whether you're thinking of choosing each arrangement of balls with equal probability, or whether you place the balls in each bin with equal probability. I would say that the most natural way to think about this is the latter, since this is most likely how it would happen in real life.

When dealing with events that are independent like the placement of the unlabelled balls, I would think about it as placing one first, then another and finally a third. This is kind of a way to artificially label the balls, that makes intuitive sense. In the real world, you would probably place the balls one after another. At the very least, you would decide which one goes where one after another. If you did decide on the arrangement of them all at once, the chances are you would not be doing so independently and the outcome you describe with probability $\frac{1}{10}$ would occur.

This idea of making events happen one after another is extremely useful throughout probability (actually, it is useful in combinatorics, to decide how many ways there are of doing things much more easily by splitting up a complicated scenario into smaller ones - it applies to probability when we have events happening with equal probability, and then the probability of an event occuring is the number of ways it can happen divided by the number of total events which could happen.)

To bring it back to your example, assuming the balls are placed independently we can say that, if we want to fill up all three bins, the first one definitely goes into a bin, the second one goes into an empty one with probability $\frac{2}{3}$ and the third one goes into the final empty one with probability $\frac{1}{3}$ giving total probability of the event $\frac{2}{9}$

If, however, we assume that each arrangement is equally likely, then we get the answer $\frac{1}{10}$. This is because some arrangements are more likely to happen then others when the balls are placed independently, so the probabilities get skewed accordingly. For example, we have already established that the event of them all being in different bins can happen in $6$ different ways. The event of them all being in the same bin can only happen in $3$ different ways because there are $3$ different bins, so it should occur with half the probability of the balls all being spread evenly. This is what causes the discrepancy in the answers.

-