تعداد جایگشت‌های از ‎۱‎ تا ‎$n$‎ که دارای عدد وارونگی‎(Inversion Number) $k$‎ هستند را ‎$I_n(k)$‎ می‌نامیم. پس خواهیم داشت ‎\begin{eqnarray*}‎ ‎I_n(0) &=& 1 \\‎ ‎I_n(1) &=& n-1 \\‎ ‎I_n\left( {n \choose 2}‎ - ‎k \right) &=& I_n(k)‎ ‎\end{eqnarray*}‎ رابطه‌ی بازگشتی زیر را برای تابع ‎$I$‎ و برای ‎$0<k<n$‎ اثبات کنید: ‎\[ I_n(k) = I_n(k-1)‎ + ‎I_{n-1}(k) \]‎

• سوال بعد
• سوال قبل