Seating without leaving gaps 8 friends are queued up to get seated for a concert, in a row of 8 seats. The first person can choose any seat, but every subsequent person must sit next to an already occupied seat. In how many ways can this be done ?

Seat the people in reverse order with the following rule: each person must sit in the most left- or right- hand empty seat.  The resulting arrangements correspond to those in the original question.
They all have two choices, except one, so there are $2^{n-1}$ possibilities overall and in this case with $n=8$ there are $128$ possibilities.
