# 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.

-
Thanks, and thanks also to others who answered. – true blue anil Sep 9 '12 at 15:05

Begin with not choosing a seat for the first person; when you will finally know where everybody is seated relative to th first person, you will know which seat she occupies. Now every person after the first has two choices: either sitting to the left or to the right of the already seated group. I'm sure you know how to count these possibilities.

[Added for clarification] Here is a contrete way to execute the procedure. Let everybody except the first person decide whether they want to sit left or right of somebody seated before them. Once that is done, a unique seating is determined giving everybody what they chose. One may count the number $l$ of choices "left", and start seating the first person in seat $l+1$ from the left, which is the only one that will allow every one of the other people to have their choice. Or alternatively, you can see that the last person has actually chosen his seat, which is iether at the left or the right end of the available seats. But then the before-last person also knows his sit, at one end of the still available seats; and so on, the "first" person gets the only seat that is destined to nobody else.

The essential point is that for combinatorial counting, it suffices to enumerate the possibilities in terms of choices that uniquely determine the outcome (and all correct outcomes should be obtained by exactly one set of choices); the choices do not have to correspond to or be in the same order, as actual choices being made.

-
If the seats are fixed, there will come a time when no more seats are available at one end, and then everyone not yet seated must fill the remaining seats (in fixed order) at the other end of the group. The simplest example is if the first person sits at one end of the set of eight seats, say seat #1. Then all the rest must choose to sit in seats $2,3,\ldots,8$ in that order. – Dilip Sarwate Sep 9 '12 at 13:12
What Marc says amounts to the following: First they train the procedure with a long empty row of seats with the first person taking a seat far from the ends. Then the remainng 7 persons have two alternatives each. Once the "training" is complete they can occupy the 8 real seats by matching the 8 seats finally used with the 8 seats available. – Hagen von Eitzen Sep 9 '12 at 13:19
Thank you @Hagen, I couldn't have said it better. – Marc van Leeuwen Sep 9 '12 at 13:21
@Hagen Thanks for the clarification. I gave a different way of arriving at the same result in a separate answer. – Dilip Sarwate Sep 9 '12 at 13:28

Number the seats from left to right as $1,2,\ldots,8$. Then, the last seat to be filled must be $1$ or $8$. So, the number of ways of filling $8$ seats is twice the number of ways of filling $7$ seats (numbered $2,3,\ldots,8$ in one case, and $1,2,\ldots,7$ in the other. Since $2$ seats can be filled in $2$ ways, $12$ or $21$, $3$ seats in $4$ ways, $123, 312, 213, 321$, etc. $n$ seats can be filled in $2^{n-1}$ ways.

-