2
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ How are the chairs arranged? Ina line? A circle? Something else? $\endgroup$ – saulspatz Aug 10 at 16:02
  • $\begingroup$ @saulspatz in a line (forgot that detail) $\endgroup$ – Moria Aug 10 at 16:05
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Can you explain a little bit more (the stars and bars problem part)? I kinda get what you're trying to say, but I don't understand how this applies to this problem. $\endgroup$ – Moria Aug 10 at 16:14
  • $\begingroup$ Do you understand stars and bars in general? $\endgroup$ – saulspatz Aug 10 at 16:15
  • $\begingroup$ yes. But I don't get how you got that the $6$ places are the bars and the $3$ chairs are the stars (indistinguishable). And not the other way around. $\endgroup$ – Moria Aug 10 at 16:21
  • $\begingroup$ Really nice answer! Thank you so much!! $\endgroup$ – Moria Aug 10 at 16:27
0
$\begingroup$

keep in mind that ${n+k-1\choose k-1}$ = ${6+3-1\choose6-1}={8\choose5}=56$

and than what you did was right $5!{8\choose5}= 6720 $

$\endgroup$
0
$\begingroup$

Once again it is a case of multinomial . Let x1 be number of chairs before 1 child, $x2$ be number of chairs between 1st and 2nd child , $x3 $between 2nd and 3rd, $x4$ between 3rd and 4th ,$x5 $between 4th and 5th, $x6 $ after 5th.

$X1 , X6 >= 0 $ ; where as $ X2 , X3, X4,X5 >=1$ :; And $ x1+x2+x3+x4+x5+x6 =7 ;$ Number of solutions of equation is number of ways empty chairs can exist I.e $ {8}\choose{3} $

And 5 children can be arranged in 5! Ways on 5 chairs. ; Total number
Ways is $$ 5!{8\choose3}= 6720 $$

$\endgroup$
  • $\begingroup$ The number of ways to write 7 as an allowable ordered sum of 6 numbers equals numbers of ways to write 7+2 = 9 as an ordered sum of 6 positive numbers equals $C(8,5)$=$C(8,3)$ by ordinary stars and bars. $\endgroup$ – Ned Aug 10 at 16:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.