Lucia Grimes

2022-07-14

In how many ways can you sit 5 people in a row of 20 seats if no 2 can sit together?
I've seen the simpler problem of just sitting 2 people in non consecutive seats. In that case, I would subtract from the total number of ways to sit the 2 persons the number of ways of sitting them together.
In this harder version of the problem,I've though of the same thing, but now considering the case were 2, 3, 4 or 5 sit together. But that seems to count duplicate cases.

cefflid6y

Expert

Step 1
Seat 5 people (A,B,C,D and E) first and then add 4 seats (denoted by s) between them so none of them are seated adjacent to each other. Now you are left with 11 seats to put in 6 places - 4 places between them or at two ends (denoted by $↑$).
$↑As↑Bs↑Cs↑Ds↑E↑$
Step 2
Now the problem is equivalent to finding the number of 6-tuples of non-negative integers whose sum is 11 for which you use stars and bars method. Lastly, there are 5! ways to arrange people in the their seats.

Ellen Chang

Expert

Explanation:
Sit the 5 people in 16 seats, and then add a seat between each pair.
This gives $\left(\genfrac{}{}{0}{}{16}{5}\right)$ as the answer.

Do you have a similar question?