به چند روش می توان اعداد ۱ تا ۱۰ را در دو ردیف ۵تایی زیر هم قرار داد به طوری که اعداد هر ستون و هر سطر به ترتیب صعودی مرتب باشن.
۱) ۱۶
۲) ۲۱
۳) ۳۲
۴) ۴۲
من خودم شمردم به بالای ۳۲ که رسیدم گزینه ۴ رو زدم ولی حلش خیلی راحت از کاتالان ۵ استفاده کرده و به جواب رسیده.از رو چی به این نتیجه رسیده که تعدادش کاتالان پنج می شه؟
پیشاپیش ممنونم.
سلام. وقت بخیر. لطفاً از این به بعد عنوان موضوعتون رو مناسب انتخاب کنید. این عنوان رو ویرایش کردم.
این سوال، سوال کنکور هم بوده. به نظرم سوال سختیه. من بصورت بازگشتی به یه نتایجی رسیدم که میشه با استقرا با کاتالان برابر دونست. شمول و طرد سنگینی هم روش میخوره. روش حلم به این شکل بود:
به ازای جمله n ام دنباله تعداد ۲n عدد داریم. یه حالت رو درنظر بگیرید که عدد ۲k در سطر بالایی و مکان k ام قرار گرفته باشه. در این حالت تمام اعداد ۱ تا ۲k-1 در پایین و سمت چپ عدد k قرار میگیرن و اعداد از ۲k+1 تا ۲n در سمت راست این عدد. (روی این جمله قبل یکم دقت کنید.)
در این حالت دنباله به دو قسمت جدا از هم تقسیم میشه و میشه اونو بازگشتی حلش کرد. رابطه بازگشتی میشه تعداد حالات قرار گرفتن عدد ۲i سر جای خودش که i از ۱ تا n متغیره. حالتی که عدد ۲k سر جای خودشه میشه حاصل ضرب جمله kام دنباله B ضربدر جمله n-kام دنباله A که جواب نهایی هم دنباله A خواهد بود.
توجه کنید که مشکل ما محاسبه B خواهد بود. چون اگه قراره تکراری هارو حساب نکنیم باید وقتی عدد ۲k سرجای خودش قرار گرفته باشه، به ازای iهای کوچکتر از k هیچکدوم از اعداد ۲i سر جای خودشون قرار نگیرن. دلیلش هم اینه که اون حالت هارو قبلاً شمردیم. دنباله B رو میشه از روی دنباله A حساب کرد.
اگه توی توضیحاتی که گفتم جایی مشکل داشتید درخدمتم.
موفق باشید.