Number of ways to arrange 5 indistinguishable balls in 12 boxes so that no two are next to each other

244 Views Asked by At

I have two ways of doing this question but they give different answers. The reasoning in one of my methods must be flawed and I would appreciate any help in pointing it out.

Method 1. First assume balls are distinguishable then divide by 5! at the end.

Number of ways to arrange 5 balls with no constraint is $12\cdot11\cdot10\cdot9\cdot8 $

Number of ways to arrange 5 balls with at least 1 ball next to each other is $$ 10\cdot2\cdot10\cdot9\cdot8+2\cdot1\cdot10\cdot9\cdot8$$

The first part comes from putting the first ball in 1 of the 10 middle boxes then putting the second ball in one of the boxes next to it and putting the remaining 3 balls anywhere.

The second part comes from putting the first ball in one of the the two end boxes, then putting the second ball next to it and the remaining 3 anywhere.

and the final answer is

$$ \frac{12\cdot11\cdot10\cdot9\cdot8-(10\cdot2\cdot10\cdot9\cdot8+2\cdot1\cdot10\cdot9\cdot8)}{5!}$$

I strongly believe this method is flawed, can someone help me point out where I went wrong.

The other method which I assume to be correct is.

$$\binom{6}{5}+2\cdot\binom{6}{4}+\binom{6}{3}$$

This one comes from arranging the blue balls in between gaps.

1

There are 1 best solutions below

0
On BEST ANSWER

You second calculation is correct. To do it the first way, you can use the principle of inclusion and exclusion, as I said. There are $12 \choose5$ ways to distribute $5$ balls. There are $11$ ways to place two balls next to one another, and then $10\choose3$ ways to distribute the remaining balls giving $${12 \choose5}-11\cdot{10\choose3}$$ ways so far. However, we have subtracted any distribution with two pairs of consecutive balls twice, so we have to add those back in. This is a bit tricky, since we could either have two pairs that don't touch, or a run of three. Once you've figured that out, you need to subtract out the distributions with three pairs. This can either be a pair and run of three or a run of four. Finally, you need to add back the distributions with four pairs, which can only be a run of five.