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

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.

• Presumably the four people are distinct as individuals, so there will be a factor of $4!$ in both answers. – hardmath Feb 25 '17 at 3:22
• @hardmath the 2nd case is anyways a permutation so 4! need not be multiplied separately – oshhh Feb 25 '17 at 3:25
• 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. – JMoravitz Feb 25 '17 at 3:29
• @JMoravitz Ah...got it, you can post this as an answer – oshhh Feb 25 '17 at 3:30

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.