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