====== سوال ۱۱ ======

یک جایگشت   ‎$p_1‎, ‎p_2‎, ‎\dots‎, ‎p_n$‎  از مجموعه  ‎$\{1‎, ‎2‎, ‎\dots‎, ‎n\}$‎
یک ‎{\ir‎  جایگشت خوب } نامیده می‌شود اگر برای هر ‎$1 \le i \le n$‎ شرایط
زیر برقرار باشد:

  * اگر ‎$ 2i \le n$‎ ، آنگاه  ‎$p_{i}\le p_{2i}$‎ 


  * اگر ‎$ 2i+1 \le n$‎ ، آنگاه  ‎$p_{i}\le p_{2i+1}$‎ .



  - ثابت کنید که اگر ‎$p$‎ یک جایگشت خوب  باشد، برای هر ‎$1 \le i \le n$‎ داریم  ‎$p_1 \le p_i$‎ .
  - ثابت کنید که  اگر ‎$p$‎ یک جایگشت خوب  باشد، تعداد اعضای مجموعه ‎$\{i \mid 1\le i \le n‎, ‎p_i \ge p_2\}$‎ بزرگ‌تر یا مساوی با     ‎$n‎ - ‎1 \over 2$‎ است.
  - اگر   ‎$n = 2^k-1$‎ باشد، ‎$T_k$‎ را مساوی با تعداد جایگشتهای خوب  مجموعه  ‎$\{1‎, ‎2‎, ‎\dots‎, ‎n\}$‎ تعریف می‌کنیم. یک رابطه بازگشتی برای محاسبه ‎$T_k$‎ پیدا کنید.



<پاسخ>




</پاسخ>

  * [[سوال ۱۰|سوال قبل]]