# 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. Oct 15, 2015 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)$? Oct 15, 2015 at 19:10