# Math Help - seats

1. ## seats

Ten women sit in 10 seats in a line. All of the 10 get up and then reseat
themselves using all 10 seats, each sitting in the seat she was in before or aseat next to the one she occupied before. In how many ways can the women be reseated?

2. ## Re: seats

Originally Posted by Veronica1999
Ten women sit in 10 seats in a line. All of the 10 get up and then reseat
[FONT=CMR10][SIZE=2][FONT=CMR10][SIZE=2][LEFT]themselves using all 10 seats, each sitting in the seat she was in before or aseat next to the one she occupied before. In how many ways can the women be [SIZE=4]reseated?
Suppose that $S_n$ is the number of ways to seat $n$ women according to the rules.
Then $S_1=1,~S_2=2$ and if $n\ge 3$ then $S_n=S_{n-2}+S_{n-1}$

Can you explain why that works?