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



فرض کنید $a$ و $b$ دو دنباله به طول $n$ و از اعداد صحیح نامنفی باشند. منظور از $a + b$ دنباله‌ای به طول $n$ است که عنصر $i$‌اُم آن حاصل‌جمع عنصرهای $i$اُم در $a$ و $b$ است $(1 \le i \le n)$. به زوج مرتب $(a, b)$ 
**جایگشت ساز**
می‌گوییم اگر و تنها اگر دنباله‌ی $a + b$ جایگشتی از اعداد ۱ تا $n$ باشد. تعداد زوج مرتب‌های $(a, b)$ جایگشت‌ساز به طول ۱۰ را بیابید که هر دو دنباله‌شان ناصعودی باشند. یک دنباله ناصعودی است اگر هر عضو از دنباله کوچک‌تر مساوی عضو پیشین باشد.



  - 1024
  - 512
  - 5632
  - 11
  - 58786






<پاسخ>
گزینه (۱) درست است.

با توجه به این‌که هر دو دنباله نا صعودی هستند می‌توان نتیجه گرفت که دنباله‌ی $c$ نیز ناصعودی است. با توجه به اینکه $c$ جایگشتی از اعداد ۱ تا $n$ است، دنباله‌ی $c$ به شکل $n, n-1, n-2, ..., 2, 1$ است.

می‌دانیم که $a_i \ge a_{i+1}$ و $b_i \ge b_{i+1}$ همچنین $c_i = c_{i+1} + 1$. پس دو حالت برای انتخاب $a_n$ و $b_n$ وجود دارد که کدام‌یک ۱ و دیگری ۰ باشد. همچنین برای هر اندیس $i$ از $n-1$ تا $0$ دو حالت وجود دارد که مقدار یک اضافه شده به اندیس $i$ به کدام یک از دو دنباله اضافه شود. پس در مجموع $2 \times 2^{n-1} = 2^n$ حالت وجود دارد.

</پاسخ>



  * [[سوال ۲|سوال بعد]]