Ways to sit 5 kids in 12 chairs lined up in a row such that none of them are next to each other

combinationscombinatoricsdiscrete mathematicspermutations

How many ways are there to sit 5 kids in 12 chairs lined up in a row such that none of them are next to each other?

My first thought was to sit the kids with an empty chair next to them:

$x_1|x_2|x_3|x_4|x_5$ (where $x_i$ are the kids and | are the chairs).

by then I have used 9 chairs.

Of course I can put a chair next to $x_1$ and another chair next to $x_5$.

There are $5!$ ways to sit the kids in 5 chairs, and then I have 3 chairs left, which can be put in any of the 6 spaces left so I arrange them as ${6}\choose{3}$.

So that would be $5!$${6}\choose{3}$$=2400$ which is wrong, because the correct answer to this would be $6720$.

Best Answer

You came close. When you have the $3$ chairs to put in $6$ places it becomes as stars and bars problem, so the answer is ${6+3-1\choose6-1}={8\choose5}=56$, which does result in $6720.$

Your solution us incorrect, because ${6\choose3}$ is the number of ways to pick three of the spots in which to put a chair. This would be OK if it were required that there be no more than two chairs between any two of the kids, but nothing prevents us from putting all three chairs between the second at third kid, for example.

We have six spots where we can put chairs, and three chairs to distribute. This is the same problem as distributing three indistinguishable balls in six distinct bins, which is solved by stars and bars.

To answer the point you raise in your last comment, the spots are distinguishable because it makes a difference if Jane and Mary are separated by two chairs or three or four, but it doesn't matter which particular chairs we put between them; the red chair and the green chair are the same as far as we are concerned in this problem.