NPR Sunday Puzzle (Mar 3, 2013): Dinner Party Musical Chairs:
Q: 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?
For this puzzle, I think we have to assume each seat position and person is unique. Also, I assume Will wants seating arrangements where each person has their own chair (no sharing). What I don't see, is why the table has to be circular. Couldn't it be square and we could still figure out how to move left or right?
Edit: The first case that might get overlooked is everyone returning to their original seat. The next two cases are where all 8 people move clockwise or counter-clockwise one seat. There can't be any other cycles involving more than two people because that would require someone to move more than one seat, so the remaining cases involve neighboring "couples" swapping seats while others stay still. All that is required is to enumerate the ways to swap couples.
A: There are 49 ways that 8 people could stand up and be reseated (link to PDF containing diagrams). Incidentally, the Online Encyclopedia of Integer Sequences has the answers for various table sizes (A0048162 = 1, 2, 6, 9, 13, 20, 31, 49...) which confirms the answer for 8 people is 49 ways.