المپدیا

برای $n=2$ و $n=3$ بررسی کنید به چه زوج‌های خواسته شده‌ای می‌توان رسید.

اگر عدد یک در ابتدای جایگشت ظاهر شود، چه زوج‌هایی را می‌توان از روی زوج‌های $n$های کوچک‌تر ساخت؟ اگر در آخر ظاهر شود چه؟

اگر عدد $n$ در ابتدای جایگشت ظاهر شود، چه زوج‌هایی را می‌توان از روی زوج‌های $n$های کوچک‌تر ساخت؟ اگر در آخر ظاهر شود چه؟

به کمک استقرا و سه راهنمایی پیشین حکمی که به‌ آن دست یافته‌اید را اثبات کنید.

به نقش عدد $n$ نگاه کنید. آیا در سمت راست $n$ می‌توانیم بهراد داشته باشیم؟‌ آیا در سمت چپ $n$ می‌توانیم پارسا داشته باشیم؟

می‌توانید تعداد جایگشت‌هایی را بشمارید که از اعداد ۱ تا $n$ تشکیل شده باشند و $a$ پارسا داشته باشند؟

برای راهنمایی ۲، از برنامه‌نویسی پویا استفاده کنید.

در ادامه‌ی راهنمایی ۳، تعریف $dp[i][j] = k$ را چنین انجام دهید که باقی‌مانده‌ی تعداد جایگشت‌هایی از $i$ عدد متمایز با $j$ پارسا بر $m$ برابر $k$ است.

از طرفی دقت کنید اگر جایگشتی $x$ پارسا داشته باشد، اگر همان جایگشت را از آخر به اول بنویسید دارای دقیقا $x$ بهراد خواهد بود.

حال از راهنمایی ۱ استفاده کنید. اگر جایگاه $n$ و مجموعه اعدادی که در سمت چپ و راست آن قرار است استفاده شوند مشخص شده باشد،‌ می‌توانید با تعریف $dp$ فوق تعداد جایگشت‌های مطلوب را بشمارید؟

حال اگر قصد داشته باشیم اعدادی که در سمت چپ $n$ ظاهر می‌شوند را مشخص کنیم،‌ چند حالت داریم؟

انتخاب فوق را به چه نحوی پیاده سازی کنیم؟ دقت کنید که $m$ لزوما اول نیست. اما الگوریتم می‌تواند از $O(n^2)$ باشد.

در ادامه‌ی راهنمایی ۷، به اتحاد پاسکال دقت کنید.

حال کافیست به ازای هر جای قرار گیری $n$ پاسخ‌ها را جمع بزنیم.

سعی کنید عدد لاتی و عدد زیبایی‌ای مثال بزنید که زیرمجموعه‌ی سازگاری با اندازه‌ی $\Omega((n-2)! \log{n})$ بیابید.

از ساده‌ترین مثال‌های عدد لاتی و عدد زیبایی شروع کنید.

اگر عدد لاتی یا عدد زیبایی برابر با ۱ باشند، کران مناسبی می‌توان یافت؟

حال که نمی‌توان از عدد لاتی و عدد زیبایی ۱ به نتیجه‌ای رسید، شاید بتوان کمی مثال‌های بزرگ‌تر را بررسی کرد.

به جایگشت‌هایی فکر کنید که عدد لاتی و عدد زیبایی آن‌ها ۲ است.

عدد $n$ در یک جایگشت را در نظر گیرید. $n$ خود هم به عدد لاتی و هم عدد زیبایی جایگشت می‌افزاید.

روی نحوه‌ی قرار گیری اعداد سمت چپ و راست دنباله حالت بندی کنید.

$\frac{1}{1} + \frac{1}{2} + ... + \frac{1}{n} \in \Omega(\log{n})$