How to seat $n$ people in $n$ seats if each person must take a seat next to an already sitting person?

Question

The question is exactly the same as in Permutations - n people and n seats

Copied here for your reference:

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?

The solution that I was provided is also identical to the accepted answer in the above link, but it's still not intuitive to me and I'm not sure if I'm thinking about it the right way.

Essentially, if, say, the first person takes the $k$th, why does $\binom{n-1}{k-1}$ guarantee the constraint (that each person must sit next to another already seated person) is satisfied?

I understand that there are $\binom{n-1}{k-1}$ to choose a distinct set of $k-1$ people to be seated on the left, but it's not clear to me why this guarantees the adjacency.

One way that I've thought about this that seems to make sense is consider person #1 sitting at the $k$th seat. For each unique set of $k-1$ people, there’s a corresponding set of $n-k$ people. There is exactly $1$ way to arrange them on the left and right, respectively, to guarantee the adjacency. Basically if we label the $n$ people as $1,2,3,4, \ldots, n$. The $k-1$ people on the left would be sorted in decreasing order, and the people on the right would be sorted in increasing order. Is this the right idea, or is there a much simpler way to think about this? I feel like I'm making this more difficult.

Answer 1

You have the right idea. Imagine that the $n$ people are queued up, and we number them by their positions in the queue. Any $k-1$ of them could be the $k-1$ that end up sitting to the left of the first person, so there are $\binom{n-1}{k-1}$ possible sets of people on that side, but as you say, there is only one possible order in which they can be seated: the one with the smallest number must have sat immediately to the left of the first person, the one with the next smallest number immediately to that person’s left, and so on, so that their numbers are decreasing from left to right. The other $n-k$ people can also be seated in only one order, since the first one of them to take a seat — the one with the lowest number — must be immediately to the right of the first person, the one with the next lowest number must be immediately to that person’s right, and so on. Thus, the entire arrangement is completely determined by which $k-1$ people are on the left of the first person, and there are therefore $\binom{n-1}{k-1}$ arrangements with the first person in seat $k$.

It’s actually the adjacency requirement that guarantees that we know the arrangement once we know which $k-1$ people are to the left of the first person: without it, there would be $(k-1)!$ possible different arrangements of those $k-1$ people.

By the way, if you look at it in these terms, what we’re counting here are permutations $\langle a_1,a_2,\ldots,a_n\rangle$ of $\{1,\ldots,n\}$ such that $a_k=1$, $a_i>a_{i+1}$ for $1\le i<k$, and $a_i<a_{i+1}$ for $k\le i<n$.

Answer 2

Each person that enters the room has exactly two possible sits (at the end of the row from both sides). Once you chose which people will choose to sit on the smaller than $k$ sits, it is clear what is the sitting arrangement.

Suppose $n=10$ and #1 sits on sit number 5. You need to choose 4 more to sit on sits 1-4, say you chose 2,3,6,8. Then: When 2 enters the room, he is chosen to sit on sits 1-4 so he must sit on 4. 3 enters, he is chosen so he must sit on 3. 4 enters. He is not chosen so he must sit on 6. 5 enters. He is not chosen, so 7 for him. 6 enters. He is chosen so he'll sit at 2. 7 will occupy 8, 8 will sit in the place labeled 1 and 9,10 in 9,10, respectively. Once the set $2,3,6,8$ was chosen, the arrangement is fixed.

Answer 3

So, lets make a string of left or right for the people to follow in that way the choice of the $i-$th person is marked. For example $LRRLL$ and so you will sequentially doing $1\rightarrow ^L 21\rightarrow^R 213 \rightarrow^R 2134\rightarrow^L 52134\rightarrow^L 652134.$ Now because exactly $k-1$ people has to be in the left, then you choose the $k-1$ positions in which you will place the $L.$