Combinatorics: Bars and Stars Confusion

Question

Suppose we have $5$ stars and $2$ bars. Assume that there can be multiple bars between the consecutive stars. Then, there are $6$ possible spots for the bars, which should mean number of different ways $= 6^2$ ($6$ spots for each bar, $2$ bar). However, the formula and the explanation online suggests it should be $7\choose 2$ = $7\choose5$, which is choosing $2$ spots out of $7$ for the bars or equivalently $5$ spots out of the $7$ for stars. I'm unable to figure out why I'm wrong?

Answer 1

Here is why the answer is not $6^2$. Your reasoning is that there are six gaps defined by the five stars, so six choices for each bar, as shown below: $$ \_\,{}_{1}\,\_ \star \_\,{}_{2}\,\_ \star \_\,{}_{3}\,\_ \star \_\,{}_{4}\,\_ \star \_\,{}_{5}\,\_ \star \_\,{}_{6}\,\_ $$ However, if you count using the formula $6\times 6$, you are effectively saying that order matters. That is, you are saying that placing the first bar in space $3$, and the second bar in space $5$, is different then placing the first bar in space $5$, and the second bar in space $3$. But order does not matter, because these both result in the same stars-and-bars arrangement: $$ \star\,\star \mid \star\,\star \mid \star $$ Here is how you fix this overcounting. First of all, set aside the six arrangements where both bars are in the same gap. Of the remaining $6\times 6-6=30$ arrangements, you must divide by $2$ to correct for double counting. Finally, you add back in the six arrangements set aside (which were not double counted). Therefore, the number of ways is $$ 6+\frac{30}2=21. $$ Indeed, this is equal to the expected answer of $\binom 72$.

Answer 2

Here is a way to obtain the count without worrying about symmetries.

Label the bars, so there is a "first bar" and a "second bar".

As you note, there are six positions for the first bar (the four inter-star positions, plus the left-most and right-most position). But once you place a bar, you effectively divide the gap into two new gaps: before the bar and after the bar. That means that after you place the first bar in one of the six positions, there are now seven positions for the second bar. Thus, the way to place two labeled bars between five stars is $6\times 7$ (rather than $6\times 6$).

But the two bars are indistinguishable; that means that you can take the labels you placed on them, shuffle them, and reapply them, to get a "different" way to place the labeled bars, but which corresponds to the same "unlabeled bar" distribution. How many ways can you put the tags on the two bars? Well, $2!$ ways. So you have to divide the total by $2!$, giving $\frac{6\times 7}{2!}$ ways.

This can be generalized to more stars and more bars. If you have $n$ stars, there are $n+1$ positions for the first bar. Each bar placed increases the number of positions for the next bar by $1$ (effectively dividing one position into two). And if you have to place $r$ bars, there are $r!$ ways of labeling them. Thus, you end up with $$\frac{n(n+1)(n+2)\cdots(n+r-1)}{r!}$$ ways of placing the bars. This happens to be the same as $$\binom{n+r-1}{r} = \binom{n+r-1}{n-1}$$ ways. (What you write as $nCk$ is the binomial coefficient $n$ choose $k$, which is also denoted $\binom{n}{k}$)

Answer 3

You can find the answer in a way close to your original thinking as follows.

There are 6 places for the first bar. Once it is placed, there are 6 items in the picture, so there are $7$ places to put the second bar. (The second bar can go before all 6 items, after the first of the $6$ items, ..., or after all $6$ items.) But the bars are indistiguishable, so every configuration has been counted twice ($2!$ times).

For example, you have counted $\star\,\star \mid_1 \star\,\star \mid_2 \star$ separately from $\star\,\star \mid_2 \star\,\star \mid_1 \star$.

So with indistiguishable bars, the number of results is $6\cdot7\over2!$.

If there were five stars and three bars, you could use the same reasoning to get the answer $6\cdot7\cdot8\over3!$, and so on.

Answer 4

If you want to know why the correct answer is $\binom72$, this is already explained in many places, such as Stars and Bars Derivation. That part of your question is a duplicate of that question and probably several others.

If you want to know what's wrong with your reasoning for $6^2$, the question you really should ask is what is right about it. If you don't take the trouble to keep track of whether you're actually making a one-to-one mapping between the set you're counting (placements of distinguishable dividers in six slots under certain constraints), you don't have a valid method, even if it happens to produce the correct number sometimes.

Here's another way to look at your method: you can just as easily put down the two dividers ("bars" or "sticks") first and then distribute the other objects ("stars" or "stones") into the spaces between and on either side of the dividers. There are $5$ objects to distribute into $3$ spaces, so your reasoning says there are $5^3 = 125$ ways to place the objects.

Now that we have two wildly different answers for the same problem, consider what justification there actually was for the methods that provided either of these answers.

---

Another approach is to try a smaller problem and actually work through all of the possible arrangements of the objects. Your method happens to give the correct answer for one divider (because $n^1 = \binom n1$), so let's try two dividers.

Two dividers and one other object. Considering the gaps between and around objects, there are $2$ places to put a divider. So your method says there are $2^2$ arrangements. But actually there are only these arrangements:

$$ |\ |\ \bullet $$ $$ | \bullet | $$ $$ \bullet\ |\ | $$

You can work out where the dividers go for each of your four ways of distributing dividers and figure out where the "extra arrangement" (that is, the error) came from.

Once you figure out two dividers and one object, try two dividers and two objects, or three dividers and one object, and so forth.

This kind of exercise is a really good way to develop mathematical intuition, so it's worth trying a method like this for yourself even after people tell you it's wrong.