Processing math: 0%

المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۲۴:ترکیبیات:سوال ۴

سوال ۴

پس از آن که سلطان مشاهده کرد اکثر دانش‌مندان مانند آووگادرو، کاتالان، رمزی و ‎\ldots‎ برای خود عددی دست و پا کرده‌اند ‎(!)‎، تصمیم گرفت او نیز عدد خودش را معرفی کند. به ازای هر عدد طبیعی ‎n‎، عدد سلطانی نوع اول که با ‎S_{1‎, ‎n}‎ نشان داده می‌شود، برابر با تعداد روش‌های قرار دادن اعداد ‎1‎, ‎2‎, ‎\ldots‎, ‎n‎ در یک جدول ‎2\times{}n‎ است؛ طوری که هر عدد دست کم یک بار بیاید و هر عدد، بیش‌تر یا مساوی اعداد سمت چپ و پایین‌ش (در صورت وجود) باشد.

  1. اگر عدد کاتالان ‎n‎ام را با ‎C_n‎ نشان دهیم، ثابت کنید: S_{1‎, ‎n}\ge{}C_n‎‎‎
  2. به ازای هر عدد طبیعی ‎n‎، عدد سلطانی نوع دوم که با ‎S_{2‎, ‎n}‎ نشان داده می‌شود، برابر با تعداد روش‌های قرار دادن اعداد ‎1‎, ‎2‎, ‎\ldots‎, ‎n‎ در یک جدول ‎2\times{}n‎ است؛ طوری که هر عدد دقیقن ‎۲‎ بار بیاید و هر عدد، بیش‌تر یا مساوی اعداد سمت چپ و پایین‌ش (در صورت وجود) باشد. اگر عدد کاتالان ‎n‎ام را با ‎C_n‎ نشان دهیم، ثابت کنید: ‎ S_{2‎, ‎n}\le{}C_n

ابزار صفحه