# Equal probabilities in each count in stars and bars

Stars and bars is a common technique used in combinatorics. It asserts that the number of ways to put $n$ indistinguishable balls into $k$ distinguishable bins is given by:

$$n + k - 1 \choose k - 1$$

I've seen this count used frequently to calculate probabilities but after some thought, I am slightly skeptical as to whether or not each of the counts given by the stars and bars has a equal probability of occurring.

Lets consider the case with 3 balls and 2 bins. I will represent different arrangements of balls with $(n_1, n_2)$ being the case where there are $n_1$ balls in bin 1 and $n_2$ balls in bin 2. Naturally, we have $0 \leq n_1, n_2 \leq 3$ and $n_1 + n_2 = 3$.

We can compute the probability of $P(0,3)$, $P(1,2)$, $P(2,1)$, and $P(3,0)$ as follows. Label each of the balls so that there are $2^3 = 8$ different equally likely arrangements.

Of these arrangements, there is only $1$ way to put $0$ balls in bin 1. There are $3$ ways to $1$ ball into bin 2, and the other two cases are symmetrical. Hence:

$$P(0,3) = 1/8 \qquad P(1,2) = 3/8$$

This shows that the different items counted in stars and bars do not occur with equal probability.

If someone would be so kinda, could you confirm this work? I believe that I have seen the usage of stars and bars to count the number of possibilities for use in the denominator of probability problems. Am I right in thinking that such a practices is incorrect?

• It is not necessarily incorrect. But I would agree that it is often incorrect. We have to start with a probabilistic model of how the balls got into the bins. In many (most?) cases has the balls thrown towards the bins one at a time, independently, with a ball equally likely to land in any bin. For that model, the various possibilities counted by Stars and Bars are, as you point out, not equally likely. – André Nicolas Oct 15 '15 at 18:42
• Stars and bars is just used to count the ways to put the balls into the bins. Didn't you just do the same thing when you determined the probabilities $P(n_1,n_2)$? – John Douma Oct 15 '15 at 19:10