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.

Question

In how many ways can you sit 5 people in a row of 20 seats if no 2 can sit together?I&#039;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&#039;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 · Accepted Answer

Step 1Seat 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   ↑).  ↑  A  s  ↑  B  s  ↑  C  s  ↑  D  s  ↑  E  ↑Step 2Now 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 · Accepted Answer

Explanation:Sit the 5 people in 16 seats, and then add a seat between each pair.This gives                     (                    16      5                      )             as the answer.