MoMath!

It's time for MoMath - that is, the Museum of Mathematics.

I first heard about MoMath from a pretty cool looking flyer. You know, the kind with some demurely (dare I say...indiesque?) coloured triangles arranged in the shape of a nautilus and stuff - like, an actual well-designed flyer, as opposed to the really nerdy stuff that we mathematicians produce most of the time. And that's all I know about MoMath.

Except the following puzzle given at the opening ceremony of this museum:

Eight people are seated around a round table (the table seats 8 precisely). They all get up at the same time (ignore physics for a moment here) and each person either moves to their left or right by one chair or stays where they are, before sitting down again (miraculously avoiding two people trying to get into the same chair). In how many distinct ways is this possible?

This was actually a question posed on the NPR Sunday Puzzles last week (hence my later than usual post, I was a tad paranoid that I'd get it wrong and waited for the official answer to be revealed :P), and the guy on the program who got it right said that he took some time over a few days bashing out all the solutions. Let's see if we can at least do this a tiny bit more efficiently.

Let's first label the positions going around the table slightly irregularly: let's order them 1, 3, 5, 7, 8, 6, 4 and 2 without loss of generality. Now, given a (legal) re-seating, we can roll-call these guys in order from 1 to 8, and just take note of the number \(\sigma\) just prior to first person who's changed their seat. The idea is that \(\sigma\) partitions our set of legal re-seatings and helps us organise our counting of legal re-seatings.

For example, if this number is 8, then everyone ends up where they started - clearly there's only one way to do this. So:

when \(\sigma=8\), there's precisely \(1\) re-seating.

Next, if \(\sigma=7\), then clearly 7 stays where s/he was seated, and since 8 can't go anywhere-else, s/he's forced to stay where s/he is - which isn't allowed, because then we'd have that \(\sigma=8\). Soo:

when \(\sigma=7\), there're precisely \(0\) re-seatings.

Now, for \(\sigma=6\), 6 stays and 7 has to move, and it's forced to switch with 8. Sooo:

when \(\sigma=6\), there's precisely \(1\) re-seating.

For \(\sigma=5\), 5 stays and 6 has to move, and it's forced to switch with 7. And by switch, I mean that 7 goes to sit where 6 started from - so...actually switch. Poor 8 is forced to stay. Soooo:

when \(\sigma=5\), there's precisely \(1\) re-seating.

For \(\sigma=4\), 4 stays and 5 has to move, and it's forced to switch with 6. We have 7 and 8 left, who're free to either switch or to stay put. Sooooo:

when \(\sigma=4\), there're precisely \(2\) re-seatings.

For \(\sigma=3\), 3 stays and 4 has to move, and it's forced to switch with 5. We have 6, 7 and 8 left, who're free to do whatever. And we could just count this as before, but if you think about it, the number of such arrangements is the same as the number of legal re-seatings where 4 and 5 are forced to stay where they started instead of switching. That is, the count for \(\sigma=3\) is the same as the the total of the legal re-seatings for when \(\sigma\geq5\). Soooooo:

when \(\sigma=3\), there're precisely \(3\) re-seatings.

For \(\sigma=2\), 2 stays and 3 has to switch with 4. So, by the same logic as for the previous count, the total number of legal seatings may be obtained by summing the legal re-seatings for \(\sigma\geq4\). Sooooooo:

when \(\sigma=2\), there're precisely \(5\) re-seatings.

For \(\sigma=1\), 1 stays and 2 switches with 3. Rinse and repeat. Soooooooo:

when \(\sigma=1\), there're precisely \(8\) re-seatings.

At this point, let's pause for a while, we've got the sequence of numbers:\begin{align}1,0,1,1,2,3,5,8\end{align} does it ring a bell? Why yes, it's (pretty much) the Fibonacci sequence. And indeed this behaviour will manifest itself should we wish to do the same computations for more people seated around the table. But for now, let's get back to the problem. So, we might mindlessly now expect that for \(\sigma=0\), that we'd end up with \(13\) re-seatings, but that it's slightly wrong. So, let's walk through our logic.

For \(\sigma=0\), we know that 1 must switch with someone. However, unlike before, it isn't forced to switch with 2, but may switch with 8 as well. Which means that we should double the \(13\) re-seatings to correct for this extra freedom. But, \(26\) is still under-counting the number of legal reseatings for \(sigma=0\) because there are 2 additional legal re-seatings which arise when everyone just moves either one seat to their left or one seat to their right. We miss these 2 possibilities in our count because we only considered the cases when 1 switches with another dude, and not when the other dude (either 2 or 8) just keeps shufflin' along.

Sooooooooo...

when \(\sigma=0\), there're precisely \(28\) re-seatings.

Making a total of \(1+0+1+1+2+3+5+8+28=49\) legal re-seatings.

So, umm...homework. Show that the the number of legal re-seatings for \(n\) people is precisely the coefficient of \(x^n\) when we expand \begin{align}\frac{1-x+3x^3-2x^4-3x^5}{1-2x+x^3}\end{align} as an infinite series around \(x=0\).

Okay, I admit that wasn't the most straight-forward proof that something was Fibonacci-esque or whatevs, but umm...just...deal with it? I guess?