10 women are sitting in a row. All of them get up and reseat themselves in a way such that each woman can sit either in the chair where she was previously sitting or in the chair right next to hers. In how many ways can the women reseat themselves?
-
UP 0 DOWN 0 0 1
1 Answers
66If f(n) denotes the number of ways that n women can sit as prescribed in n chairs, then its easy to see that
f(n) = f(n-1) + f(n-2)
(the same recurrence satisfied by Fibonacci sequence!!) Also, f(1) = 1 and f(2) = 2. As such one gets f(10) = 89.