We have $13$ chairs for $13$ people. The first person to arrive can sit in any of $13$ chairs. The next ones must always sit next to a person that is already there. If the order of arrival does not change, in how many ways we can distribute the people in these chairs?
I already found the answer because of the pattern, what I really need is how to think this problem mathematically.
Best Answer
Once the first person sits, each person among the other $12$ has at most two options: either sit on the left side of the leftmost seated person, or sit on the right side of the rightmost seated person.
Naïvely, you might suppose this gives you $13(2^{12}).$ But that fails to account for the fact that if the leftmost seat is already occupied, the next person can only sit on the right side of the rightmost person. (A similar restriction occurs when the rightmost seat is occupied.) In fact, if the first person sits in the leftmost seat, none of the others has any choice; they can only sit on the right side of the previous person.
To be precise, if the first person sits in the $k$th seat counting from the left ($1 \leq k \leq 13$), then exactly $k - 1$ people must sit on someone's left and $13-k$ must sit on someone's right. The number of ways that can occur is the binomial coefficient $\binom{12}{k - 1}.$
So we could add up all the possible seating arrangements for each of the possible choices of the first person as follows: $$\binom{12}{0} + \binom{12}{1} + \binom{12}{2} + \binom{12}{3} + \cdots + \binom{12}{11} + \binom{12}{12}.$$ You may be familiar with the fact that this sum of binomial coefficients is equal to $2^{12}.$ There is another way to see this, however: any sequence of $12$ choices of "left" or "right" is possible, and for each such sequence there is one and only one place the first person may sit such that the sequence is possible. Thus once we know the $12$ choices made by the other people, we know the first person's choice too. So we can exactly describe each possible arrangement by one of the $2^{12}$ sequences of $12$ "left" or "right" choices, that is exactly how many possible arrangements there are.