سوال ۱۱

یک جایگشت ‎$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}$‎ .

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

• سوال قبل