# We have 13 chairs for 13 people. If the order of arrival does not change, in how many ways can we distribute the chairs?

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.

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.

• Nicely explained. Commented Dec 21, 2018 at 10:24

This is if the chairs are in a circle:

My claim is that at any point in time, the people already sitting must form one block. Note in order for this to be false, someone would have had to originally sit in a chair where there was no one on either side, or else it would be connected to the original block. Thus, at any point in time, the row of people is in $$1$$ block, and thus has $$2$$ possible places where someone new can sit (next to the person on either edge).

The first person has $$13$$ choices to sit (anywhere). From now on, every person has $$2$$ places to sit (on the edges). Thus, we may think our answer is $$13 \times 2^{13-1} = 13 \times 2^{12}$$, but we have to realize that at the end, there is only $$1$$ spot left, so the last person doesn't have a choice, and thus the answer is actually $$13 \times 2^{13-2} = \boxed{13 \times 2^{11}}$$.

• Note that $13-2=11\neq10.$ But you still have overcounted, because it is not only the last person who might not have a choice where to sit. Consider what happens if the first person to arrive sits in the leftmost chair. Commented Dec 21, 2018 at 5:19
• Oh my I'm sorry for the typo. There wasn't a configuration for the chairs so I assumed they were in a circle (sorry my background gave me this indication). Commented Dec 21, 2018 at 23:44
• Looking at the question, I do not see where it says how the chairs are arranged. So they could be in a circle. Commented Dec 22, 2018 at 2:16