1
$\begingroup$

In how many ways can 4 people occupy 10 chairs in a row if no two sit on adjacent chairs

I can think of 2 ways to solve this question both giving different answers but I don't know why they're not one-on-one:

Way 1:
4 People take 4 chairs and sit with 3 chairs in the space between them:
_ |P| C_ |P| C_ |P| C_ |P|_ where '_' indicates a space for another chair. Now we have 3 chairs remaining which can be placed in $\binom{5}{3}$ ways. But the people can exchange their seats in 4! ways. Hence total permutations= 10*4!=240

Way 2:
The other way is to keep 6 chairs. Now 4 people can be seated in the 7 spaces between thee chairs. _C_C_C_C_C_C_. There are 4 people and 7 spaces so total permutations=$^7P_4$=840

I want to know why these ways do not lead to the same answer and what arrangements am I missing in the first way.

$\endgroup$
  • $\begingroup$ Presumably the four people are distinct as individuals, so there will be a factor of $4!$ in both answers. $\endgroup$ – hardmath Feb 25 '17 at 3:22
  • $\begingroup$ @hardmath the 2nd case is anyways a permutation so 4! need not be multiplied separately $\endgroup$ – oshhh Feb 25 '17 at 3:25
  • 2
    $\begingroup$ Your way1 does not count arrangements with many chairs next to one another, for example it doesn't count the arrangement |P|CCCC|P|C|P|C|P|, instead only allowing a single "extra" chair to be placed in each empty spot. Use stars and bars instead for how to distribute the extra chairs. $\endgroup$ – JMoravitz Feb 25 '17 at 3:29
  • $\begingroup$ @JMoravitz Ah...got it, you can post this as an answer $\endgroup$ – oshhh Feb 25 '17 at 3:30
2
$\begingroup$

Your way1 does not count arrangements with many chairs next to one another, for example it doesn't count the arrangement |P|CCCC|P|C|P|C|P|, instead only allowing a single "extra" chair to be placed in each empty spot. Use stars and bars instead for how to distribute the extra chairs.

Approaching the same, we have $\underline{~}PC\underline{~}PC\underline{~}PC\underline{~}P\underline{~}$ and we wish to distribute three extra chairs to these five empty spaces (with possibly multiple going to the same empty spot).

By stars and bars we have $\binom{5+3-1}{5-1}=\binom{7}{4}$ number of ways to do so. Multiplying by the number of ways to arrange the persons themselves among the seats labeled $P$ we have a total of $4!\binom{7}{4}=~^7P_4=840$ arrangements, same as the other answer.

$\endgroup$
1
$\begingroup$

You have 10 chairs, 4 individuals. They can't sit next to each other. Assuming the chairs aren't in a circular shape, you need to consider dots separating the people which you can arrange in 10 chairs. Since these empty spots can be repeated, as in 2 chairs or more between individuals, this is an unordered with repeat combinatorix question. Furthermore, all must be seated, or 5 separators to accomodate the dots.

This is then (9+5-1)C5 or 13C5 ways to place 4 people on 10 chairs with none next to each other.

Try the above reasoning with 4 chairs and 2 persons which is (3+2-1)C2 which is 6

$\endgroup$

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.