سوال ۴

پس از آن که سلطان مشاهده کرد اکثر دانش‌مندان مانند آووگادرو، کاتالان، رمزی و $\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$