$16$ people sit around a circular table. After some time, they all stand up and sit down in either the chair they were previously sitting on or on a chair next to it. Determine the number of ways that this can be done. Note: two or more people cannot sit on the same chair.
Problem
Source:
Tags: combinatorics
triskaidecahedron
28.04.2015 23:45
No; I realise your 3 examples are everyone sitting in the same chair, all moving to the right, or all moving to the left, but there are many more, e.g. if everyone stayed where they were except 2 adjacent people who swapped chairs.
triskaidecahedron
28.04.2015 23:56
Here are some hints/observations: -After the standing up and sitting down, every seat must be taken by exactly one person. -If person on seat k stays where he is, then either person k+1 will stay where he is, or he will swap with person k+2 (similarly for k-1 and k-2). -It would be helpful to call a group of people who swap their chairs a 'group'. Then on each side of a group are either 2 more groups, 2 more people who stay where they are (called statues) or a combination of both. -There are even number of statues. -Specifically, the number of statues cannot equal 1. -Try using these facts to build a recursion (also noting that it may be helpful to split into 2 cases, one with 0 statues, one with more than 0 statues, to get a grasp of the problem).
flyingpurplepeopleeater
03.06.2015 08:00
There clearly cant be more than 8 groups, so we can say there are 8c8 ways if there are 8 groups. If there are 7 groups, 9c7 ways, if 6, 10c6...etc, if 0, 16c0. Adding these up, we get 1597. However, this only takes into account groupings of 2. So this does not include everyone moving, but includes everyone sitting still. So we add 2 to get $\boxed{1599}$.