تعداد حالات ممکن برای نشستن $n$ بچه روی $n$ صندلی به شرطی که فاصله آنها حداکثر یک صندلی باشد

اینکه فاصله هر بچه از بچه قبلی حداکثر یک باشد یعنی اگر فرض کنیم بچه $i$-ام در صندلی $\pi(i)$ و بچه $j$-ام در صندلی $\pi(j)$ هستند، اگر دو بچه در ابتدا کنار هم بودند یعنی

$|i-j|=1$

آنگاه حداکثر یک صندلی بین صندلی‌های آنها باشد یعنی

$|\pi(i)-\pi(j)| \leq2$

پس فرض کنیم $P_n$ تعداد جایگشت‌های $\pi$ از $\{1,2, \ldots , n\}$ باشد به طوری که برای هر $i$ و $j$ در $\{1,2, \ldots , n\}$ اگر

$|i-j|=1$

آنگاه

$|\pi(i)-\pi(j)| \leq2$

نشان دادیم که برای $n\geq2$، مقدار

$P_{n+5}-P_{n+4}-P_{n+3}+P_{n}$

به $n$ بستگی ندارد و همواره داریم

$P_{n+5}-P_{n+4}-P_{n+3}+P_{n}=4$

بنابراین

$P_{n+5}=P_{n+4}+P_{n+3}-P_{n}+4$

فرض کنیم $P_n$ تعداد جایگشت‌های $\pi$ از $\{1,2, \ldots , n\}$ باشد به طوری که برای هر $i$ و $j$ در $\{1,2, \ldots , n\}$ اگر

$|i-j|=1$

آنگاه

$|\pi(i)-\pi(j)| \leq2$

می‌خواهیم نشان دهیم که برای $n\geq2$، مقدار

$P_{n+5}-P_{n+4}-P_{n+3}+P_{n}$

به $n$ بستگی ندارد و مقدار آن را بیابیم.

ابتدا فرض کنیم $n \geq 3$. ما جایگشت‌های $\pi$ که با $P_{n}$ شمرده می‌شوند را به شکل دنباله‌ی زیر می‌نویسیم

$\pi(1), \pi(2), \ldots , \pi(n)$

فرض کنیم

$U_{n}$ تعداد جایگشت‌های شمرده شده با $P_{n}$ باشد که با $n-1,n$ تمام می‌شوند،

$V_{n}$ تعدادی باشد که با $n,n-1$ تمام می‌شوند،

$W_{n}$ تعدادی باشد که با $n-1$ شروع و با $n-2,n$ تمام می‌شوند،

$T_{n}$ تعدادی باشد که با $n-2,n$ تمام می‌شوند ولی با $n-1$ شروع نمی‌شوند و

$S_{n}$ تعدادی باشد که $n-1,n$ را به طور متوالی با این ترتیب دارد ولی نه در ابتدا یا انتهای جایگشت.

واضح است که هر جایگشت $\pi$ شمرده شده با $P_{n}$ دقیقا در یکی از مجموعه‌های شمرده شده با $U_n ,V_n, W_n, T_n, S_n$ قرار دارد و یا معکوس چنین جایگشتی است. بنابراین

$P_n =2(U_n + V_n + W_n + T_n + S_n)$