2
$\begingroup$

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 ?

3 Answers 3

5

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.

  • 0
    Thanks, and thanks also to others who answered.2012-09-09
2

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.

  • 0
    @Hagen Thanks for the clarification. I gave a different way of arriving at the same result in a separate answer.2012-09-09
1

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.