Possible Duplicate:
How many ways are there for 8 men and 5 women to stand in a line so that no two women stand next to each other?

Given 5 children and 8 adults, how many different ways can they be seated so that no two children are sitting next to each other.

My solution: Writing out all possible seating arrangements:

tried using $\displaystyle \frac{34*5!*8!}{13!}$ To get the solution, because $13!$ is the sample space. and $5!$ (arrangements of children) * $34$ (no two children next to each other) * $8!$ (# of arrangements for adults).

  • 2
    $\begingroup$ Are they sitting in a line, or around a circle? or in two rows, one of 7 people and one of 6? or some other configuration? It makes a difference. $\endgroup$ – Gerry Myerson Mar 6 '12 at 23:27
  • $\begingroup$ just one single row. $\endgroup$ – user996522 Mar 7 '12 at 3:49

We have $8$ nice comfortable chairs for the adults, separated by some space. This determines $9$ "gaps" where a kid can drag a stool. (It is $9$ because a kid can drag as stool between two adult chairs, or to the left end or to the right end.)

The seating arranger chooses $5$ of these places to put a stool into. This can be done in $\binom{9}{5}$ ways. For each of these ways, the adults can be seated in $8!$ orders, and for every way to do this, the children can occupy the stools in $5!$ orders. The number of ways is therefore $$5!8! \binom{9}{5}.$$

  • $\begingroup$ Much more elegant than my solution. $\endgroup$ – Brett Frankel Mar 6 '12 at 23:47
  • $\begingroup$ @Brett Frankel: The idea of the solution I wrote down is not substantially different from yours. $\endgroup$ – André Nicolas Mar 6 '12 at 23:52
  • $\begingroup$ Same idea, much simpler presentation. $\endgroup$ – Brett Frankel Mar 6 '12 at 23:54
  • 1
    $\begingroup$ There is a convention that people are different. Am not so sure it should apply to kids (kidding). $\endgroup$ – André Nicolas Mar 7 '12 at 4:35
  • 1
    $\begingroup$ If the question were: There are $13$ chairs. How many ways can we reserve seats for the kids (with the assumptions of the original problem, we want to keep the kids apart). Then indeed the number of ways is $\binom{9}{5}$. $\endgroup$ – André Nicolas Mar 7 '12 at 5:04

The solution below assumes the seats are in a row:

This is a stars and bars problem. First, order the children (5! ways). Now, suppose the adults are identical. They can go in any of the places on either side or between of the children. Set aside 4 adults to space out the children, and place the other 4 in any arrangement with the 5 children; there are $\binom{9}{4}$ ways to do this. Finally, re-order the adults. So we get $$8!5!\binom{9}{4}$$


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