| I spent the first part of the week in Berkeley visting my friend David who's out there studying applied mathematics in the context of hydrology. Not too surprisingly, we did quite a bit of mathematics. On a hike, we chewed over NPR's Perfectly Puzzling question of the week: Eight people are seated at a circular table. Each person gets up and sits down again — either in the same chair or in the chair immediately to the left or right of the one they were in. How many different ways can the eight people be reseated? |  |
Dave crushed this thing in two parts, and since NPR's solution was along the lines of "count 'em up" and didn't give a formula for the case when you have $n$ people at the table, I figured I'd write up his solution.
Let $C_n$ be the number of ways to seat $n$ people at a circular table according to the restrictions laid out in the problem statement. One hard thing to deal with here is the fact that the table is circular. Dave's first good idea was to break the symmetry. Without loss of generality, choose 2 adjacent people at the table. Now, in each valid configuration, either these two people switch places or they don't, and, most importantly, the remaining people can be thought of sitting in a line rather than a circle. Each case defines a subproblem that is really tractable.
We define a new and related problem: how many ways are there to reseat $n$ people seated in a line such that each person switches either with their left-hand or right-hand neighbor or remains in their original spot? Define $L_n$ to be the number of ways to seat $n$ people according to these restrictions. Noting $L_1 = 1$ and $L_2 = 2$, we can go forward with induction. Suppose $L_k$ is known for $k < n$ and consider $L_n$. In each valid seating arrangement, either the $n^{th}$ person switches with her neighbor or she does not. In the case where she does not, her neighbor is unconstrained by her presence, and so there are $L_{n-1}$ ways to reseat the remaining $n-1$ people. In the case where she and her neighbor switch positions, the remaining $n-2$ are free to sit however they like subject to the rules in the problem statement, and so there are $L_{n-2}$ ways to reseat them. Assembling our cases gives $L_n = L_{n-1} + L_{n-2}$. Note that this means solutions to this subproblem are Fibonacci numbers! (Our indexing here is off by one, so that $L_n = F_{n+1}$ for $n \geq 1$.)
With this new result in hand, let's turn our attention back to the original problem. Recall that we arbitrarily chose a pair of adjacent people at the table. If the pair does not switch, then all $n$ people at the table are free to reorder themselves as if they were seated in a line. Thus, there are $L_n$ ways to reseat the table if the chose pair does not switch. If they do switch, the remaining $n-2$ people at the table are free to reorder themselves as if they were seated in a line, and so there are $L_{n-2}$ ways to reseat the table in this case. We also must account for the fact that the entire table can rotate either one seat to the right or one seat to the left. So the total number of ways to reseat the table is $C_n = L_n + L_{n-2} + 2$.
With this new result in hand, let's turn our attention back to the original problem. Recall that we arbitrarily chose a pair of adjacent people at the table. If the pair does not switch, then all $n$ people at the table are free to reorder themselves as if they were seated in a line. Thus, there are $L_n$ ways to reseat the table if the chose pair does not switch. If they do switch, the remaining $n-2$ people at the table are free to reorder themselves as if they were seated in a line, and so there are $L_{n-2}$ ways to reseat the table in this case. We also must account for the fact that the entire table can rotate either one seat to the right or one seat to the left. So the total number of ways to reseat the table is $C_n = L_n + L_{n-2} + 2$. With a little massaging, we can get a statement for $C_n$ that is recursive.
$$\begin{align*} C_n - C_{n-1} &= L_n + L_{n-2} + 2 - L_{n-1} - L_{n-3} - 2 \\
&= L_{n-2} + L_{n-4} \\
&= C_{n-2} - 2 \\
C_n &= C_{n-1} + C_{n-2} - 2.
\end{align*}$$
For base cases, we have $C_3 = 6$ and $C_4 = 9$. Sure enough, $C_8 = L_8 + L_6 + 2 = F_9 + F_7 + 2 = 34 + 13 + 2 = 49$, just as NPR claimed. For a long list of values, see the OEIS page.
Really nice proof, especially for one that Dave busted out while hiking.
Let $C_n$ be the number of ways to seat $n$ people at a circular table according to the restrictions laid out in the problem statement. One hard thing to deal with here is the fact that the table is circular. Dave's first good idea was to break the symmetry. Without loss of generality, choose 2 adjacent people at the table. Now, in each valid configuration, either these two people switch places or they don't, and, most importantly, the remaining people can be thought of sitting in a line rather than a circle. Each case defines a subproblem that is really tractable.
We define a new and related problem: how many ways are there to reseat $n$ people seated in a line such that each person switches either with their left-hand or right-hand neighbor or remains in their original spot? Define $L_n$ to be the number of ways to seat $n$ people according to these restrictions. Noting $L_1 = 1$ and $L_2 = 2$, we can go forward with induction. Suppose $L_k$ is known for $k < n$ and consider $L_n$. In each valid seating arrangement, either the $n^{th}$ person switches with her neighbor or she does not. In the case where she does not, her neighbor is unconstrained by her presence, and so there are $L_{n-1}$ ways to reseat the remaining $n-1$ people. In the case where she and her neighbor switch positions, the remaining $n-2$ are free to sit however they like subject to the rules in the problem statement, and so there are $L_{n-2}$ ways to reseat them. Assembling our cases gives $L_n = L_{n-1} + L_{n-2}$. Note that this means solutions to this subproblem are Fibonacci numbers! (Our indexing here is off by one, so that $L_n = F_{n+1}$ for $n \geq 1$.)
With this new result in hand, let's turn our attention back to the original problem. Recall that we arbitrarily chose a pair of adjacent people at the table. If the pair does not switch, then all $n$ people at the table are free to reorder themselves as if they were seated in a line. Thus, there are $L_n$ ways to reseat the table if the chose pair does not switch. If they do switch, the remaining $n-2$ people at the table are free to reorder themselves as if they were seated in a line, and so there are $L_{n-2}$ ways to reseat the table in this case. We also must account for the fact that the entire table can rotate either one seat to the right or one seat to the left. So the total number of ways to reseat the table is $C_n = L_n + L_{n-2} + 2$.
With this new result in hand, let's turn our attention back to the original problem. Recall that we arbitrarily chose a pair of adjacent people at the table. If the pair does not switch, then all $n$ people at the table are free to reorder themselves as if they were seated in a line. Thus, there are $L_n$ ways to reseat the table if the chose pair does not switch. If they do switch, the remaining $n-2$ people at the table are free to reorder themselves as if they were seated in a line, and so there are $L_{n-2}$ ways to reseat the table in this case. We also must account for the fact that the entire table can rotate either one seat to the right or one seat to the left. So the total number of ways to reseat the table is $C_n = L_n + L_{n-2} + 2$. With a little massaging, we can get a statement for $C_n$ that is recursive.
$$\begin{align*} C_n - C_{n-1} &= L_n + L_{n-2} + 2 - L_{n-1} - L_{n-3} - 2 \\
&= L_{n-2} + L_{n-4} \\
&= C_{n-2} - 2 \\
C_n &= C_{n-1} + C_{n-2} - 2.
\end{align*}$$
For base cases, we have $C_3 = 6$ and $C_4 = 9$. Sure enough, $C_8 = L_8 + L_6 + 2 = F_9 + F_7 + 2 = 34 + 13 + 2 = 49$, just as NPR claimed. For a long list of values, see the OEIS page.
Really nice proof, especially for one that Dave busted out while hiking.
RSS Feed
