3

Actually, it seams pretty simple, but I just can't figure it out.

Imagine we have a room containing $n$ seats in a row and $n$ people waiting in front of the room. The first person that enters the room can decide where he wants to sit. The remaining $(n-1)$ people must take a seat next to an already sitting person. What is the number of ways to sit all the people in the room?

Any ideas?

amWhy
  • 209,954
tradt
  • 41

2 Answers2

4

The constraint "take a seat next to an already sitting person" implies that there are no gaps between occupied seats.

Let us assume that there are $K$ ways to place $n$ people. If we increase the number of people to $n+1$, we can add the seat from the right or from the left and thus increase the number of ways from $K$ to $2K$. For $n=1$ we start with $K=1$. Therefore, for $n$ we get $K=2^{n-1}$.

Axel Kemper
  • 4,943
1

Whenever a person enters, he/she can decide to sit at a seat to the left of everyone who is already sitting, or to the right of everyone sitting. Suppose the first person sits on the $k^{th}$ seat from the left, exactly $k-1$ people can go and sit to the left side seat. Thus, the number of seating arrangements with the first person sitting on the $k^{th}$ seat from the left is $\binom{n-1}{k-1}$. Adding all these individual solutions for $k=1,2,...,n$ gives, the total number of seating arrangements as $\binom{n-1}{0} + \binom{n-1}{1} + ... + \binom{n-1}{n-1} = 2^{n-1}$

Ojas
  • 2,146
  • 1
    It's not clear to me how $\binom{n-1}{k-1}$ maintains the correct, ordering, could you please expand on this? – David Jul 26 '20 at 07:54
  • 2
    @David: Once the first person sits down (say, in the $k$th seat), there are $n-1$ open seats, of which $k-1$ are on the right. Each of the remaining $n-1$ people, as they come up, have only two choices: They can sit to the left of the leftmost person (if that seat is available), or to the right of the rightmost person (if that seat is available). Therefore, the final arrangement depends only on the sequence of L(eft) and R(ight) they choose; we can denote this sequence by writing $n-1$ symbols in a row, of which $k-1$ are L and $n-k$ are R. There are $\binom{n-1}{k-1}$ such sequences. – Brian Tung Jul 26 '20 at 19:31
  • 1
    This then needs to be summed up over all possible values of seat indices $k$ from $1$ to $n$ that the first person could have chosen, yielding $2^{n-1}$. – Brian Tung Jul 26 '20 at 19:33