Rindā ir \(12\) krēslu; uz katra no tiem sēž pa skolēnam. Skolēniem vienu reizi atļauts piecelties un apsēsties citā kārtībā, pie tam katrs drīkst apsēsties vai nu iepriekšējā vietā, vai tieši blakus iepriekšējai vietai.
Cik dažādi skolēnu izvietojumi iespējami pēc pārkārtošanās?
Apzīmēsim atbilstošu pārkārtojumu skaitu \(n\) skolēnu gadījumā ar \(a_{n}\). Acīmredzami, \(a_{1}=1\) un \(a_{2}=2\).
Apskatīsim \(n+2\) skolēnus (\(n \geq 1\)). Visi pārvietojumi iedalās divās daļās:
(A) pirmais skolēns paliek uz vietas. Tad pārkārtojas tikai nākošie \(n+1\) skolēni. Šādu pārkārtojumu pēc definīcijas ir \(a_{n+1}\).
(B) pirmais skolnieks pāriet uz otro krēslu. Tad uz pirmo krēslu pāriet skolēns no otrā krēsla. Pārējie \(n\) skolēni pārkārtojas "savā starpā". Tādu pārkārtojumu pēc definīcijas ir \(a_{n}\).
Tātad \(a_{n}+2=a_{n+1}+a_{n}\). Iegūstam \(a_{3}=1+2=3,\ a_{4}=5,\ a_{5}=8,\ a_{6}=13,\ a_{7}=21,\ a_{8}=34,\ a_{9}=55,\ a_{10}=89\), \(a_{11}=144, \mathbf{a_{12}=233}\).