سوالات المپیاد:دوره ی تابستان:دوره ی ۱۹:ترکیبیات:سوال ۶
سوال ۶
تعداد جایگشت‌های از ۱ تا n که دارای عدد وارونگی(Inversion Number) k هستند را In(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)
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
