Permutations & Combinations
Seating women in adjacent seats — Fibonacci-type count
MJAT_TS4_P1
Grade 12
Question:
Ten women sit in 10 seats in a line. All 10 get up and then reseat themselves using all 10 seats, each sitting in the seat she was in before or a seat next to the one she occupied before. The number of ways the women can be reseated is:
A) 89
B) 90
C) $2^{10}$
D) 91
Step-by-Step Solution
Key Concept: Let $S_n$ be the number of valid permutations of $n$ women. $S_1=1$, $S_2=2$. The recurrence: if woman $n$ stays in seat $n$, the first $n-1$ can be arranged in $S_{n-1}$ ways; if women $n$ and $n-1$ swap, the first $n-2$ can be arranged in $S_{n-2}$ ways. So $S_n=S_{n-1}+S_{n-2}$ (Fibonacci).
$S_{10}=F_{11}=\mathbf{89}$. Answer: A.
Correct Answer: A