Seating 7 students on 10 chairs so that no empty chairs are adjacent.

Question

Question

10 chairs have been arranged in a row. 7 students are to be seated in 7 of them so that no two students share a common chair. Find the number of ways this can be done if no two empty chairs are adjacent.

What I tried

At first 5 students out of 7 could​ be seated in $\binom{7}{5}$ ways such that alternate chairs are empty. Now, 5 remaining chairs could be filled up in $\binom{5}{2}$ ways.Now, all 7 students could permits in $7!$ ways.

$\therefore$Total number of ways=$\binom{7}{5}\cdot\binom{5}{2}\cdot7!$

But, The given answer is $7!\cdot\binom{8}{3}$

Please indicate my mistake or please post a solution if I am thinking entirely wrong.

Answer 1

Here is one way to think about this:

Forget about the $7$ chairs the students are sitting on.

Once you line up the $7$ students (which can be done in $7!$ ways), then you need to place 3 empty chairs among them, where those chairs can be between, left, or right of those 7 students (so there are $8$ positions for a chair), and you cannot have two empty chairs in the 'same' of those $8$ positions ... so you need to pick $3$ out of $8$ possible positions for the empty chairs, which can be done in $8 \choose 3$ ways. (so the latter part is a 'stars and bars' problem with $7$ stars and $3$ bars where the bars cannot be next to each other but can be at the ends).

Total:

$$7!\cdot {8 \choose 3}$$

Answer 2

Selecting $3$ not adjacent chairs out of a row of $10$ comes to finding the number of sums $a+b+c+d=7$ where $a,d$ are nonnegative integers and $b,c$ are positive integers.

Here e.g. $a$ stands for the number of not selected chairs at left side of the utmost left selected chair.

• Example1: $a=1,b=3,c=2,d=1$ represents $s|e|s|s|s|e|s|s|e|s$.
• Example2: $a=0,b=4,c=2,d=1$ represents $e|s|s|s|s|e|s|s|e|s$.

Here $s$ stands for "seated" and $e$ for "empty".

It comes to the same as finding the number of sums $a+b'+c'+d=5$ where $a,b',c',d$ are nonnegative integers and with stars and bars we find $\binom{5+3}3$ possibilities for that.

There are $7!$ arrangements for the students so we end up with $\binom837!$ possibilities.