المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۱۹:ترکیبیات:سوال ۶

سوال ۶

تعداد جایگشت‌های از ‎۱‎ تا ‎$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) \]‎


ابزار صفحه