اعداد کاتالان | تعبیرستان
اعداد کاتالانعلم و فناوریدانستنیها
×
بستن

اعداد کاتالان

در این مقاله ،اعداد کاتالان را معرفی کرده و چند مساله که جواب آن ها منجر به این اعداد می شوند را مورد بررسی قرار می دهیم...
شاید در ریاضیات گسسته با مسأله ی زیر برخورد کرده باشید:
مسأله: یک صفحه ی شطرنجی n×n در نظر بگیرید؛ می خواهیم با حرکت روی خطوط صفحه ی شطرنجی، از نقطه ی A در گوشه ی سمت چپ پائین صفحه، شروع کرده و به نقطه ی B در گوشه ی سمت راست بالای صفحه برسیم. شرط کار این است که فقط می توانیم به سمت های راست و بالا حرکت کنیم و هرگز نباید به بالای قطر AB برویم. به چند طریق می توان از A به B رسید؟
طرح این مسأله، انگیزه ای برای معرّفی مفاهیم زیر می باشد.
تعریف: برای ،n امین عدد کاتالان(ریاضی دان بلژیکی) عبارت است از: .
▪ تعریف: همان طور که می دانیم هرکلمه از تعدادی حرف تشکیل شده است. اگر حرف های تشکیل دهنده ی کلمات را x و y بگیریم، یک کلمه ی Dyck به طول عبارت است از کلمه ای که از n تا x و n تا y تشکیل شده است و در هیچ قطعه ی آغازی کلمه، تعداد yها بیش تر از تعداد xها نمی باشد.
▪ مثلاً: کلمه ی xyyx یک کلمه ی Dyck نمی باشد چون در قطعه ی آغازی xyy تعداد yها از تعداد xها بیش تر است. امّا xyxyxy یک کلمه ی Dyck است.
▪ قرارداد: از این به بعد کلمه ی Dyck را با DW و کلمه ای که خاصیّت Dyck ندارد را با NDW نشان می دهیم.
مسأله: چند DW به طول می توان نوشت؟
▪ حلّ: تعداد کلّ کلماتی به طول که می توان با n تا x و n تا y نوشت برابر است با .[چرا؟].از طرفی اگر یک NDW دلخواه در نظر بگیریم؛ پس یک قطعه ی آغازی از این کلمه وجود دارد که در آن تعداد yها بیش تر از تعداد xها است. اگر اوّلین قطعه ی آغازی که این شرط را دارد در نظر بگیریم و تمامی xهایی که پس از این قطعه ظاهر می شوند را با y و تمامی yها را [در صورت وجود] با x عوض کنیم پس کلمه ای با ۱-n تا x و ۱+n تا y خواهیم داشت [چرا؟].
از طرفی اگر کلمه ای دلخواه به طول متشکل از ۱-n تا x و ۱+n تا y داشته باشیم ،اولین قطعه ی آغازی این کلمه که تعداد y ها یکی بیش تر از تعداد x هاست در نظر بگیرید و تمامی y هایی که بعد از این قطعه ظاهر می شوند را با xو تمامی x ها را [در صورت وجود] با y عوض کنید. کلمه ی حاصل یک NDW است [چرا؟] .
در واقع این روش یک تناظر یک به یک بین کلماتی به طول شامل ۱-n تا x و ۱+n تا y و NDWهای به طول برقرار می کند. چون به تعداد کلمه ی به طول شامل ۱-n تا x و ۱+n تا y داریم ، پس تعداد NDW های به طول برابر است با . امّا تعداد DWها برابر است با اختلاف تعداد کلّ کلمات و تعداد NDWها، پس :
▪ تعداد DWهای به طول
اکنون به مسأله ای که در آغاز مقاله مطرح کردیم، برمی گردیم.
اگر حرکت به سمت راست را با x و حرکت به سمت بالا را با y نشان دهیم پس تعداد راه های رسیدن از A به B [با توجه به شرط مسأله]برابر است با تعداد DWهای به طول که همانا می باشد.
مسأله ای دیگر: به چند طریق می توان با n جفت پرانتز ( )؛ عبارت های با معنی نوشت؟
مثلاً برای ۳و ۲و ۱=n داریم:
ـ ۱=n ( ) .
ـ ۲=n (( )) و ( ) ( ) .
ـ ۳=n (( )) ( ) و ( ) (( )) و ( ) ( ) ( ) و ((( ))) و ( ( ) ( ) ) .
اگر به جای )، x و به جای (، y قرار دهیم آن گاه تعداد عبارت های با معنی با n جفت پرانتز با تعداد DWهای به طول برابر خواهد بود و این یعنی برابر است.
تاکنون حلّ سه مسأله منجر به اعداد کاتالان شده است، در ذیل توجّه شما را به دو نمونه ی دیگر جلب می کنیم:
الف) تعداد راه های مختلف پرانتز گذاری بین ۱+n نماد ریاضی عبارت است از .
به عنوان مثال اگر a و b و c و d چهار نماد ریاضی باشند، روش های مختلف پرانتز گذاری بین آن ها از این قرار است:
ب) یک ۲+n ضلعی محدّب در نظر بگیرید. با وصل کردن رأس ها، می توان این چند ضلعی را به مثلث هایی افراز کرد.
به عنوان مثال برای ۳=n داریم :
ـ با توجه به روند مقاله، آیا می توانید تعداد راه های متفاوت افراز را حدس بزنید؟ بله درست حدس زدید، تعداد روش های متفاوت افراز عبارت است از .
اعداد کاتالان در مسأله های دیگری از جمله شمارش درخت ها در نظریه گراف یا شمارش نوع خاصی از افراز های مجموعه های متناهی نیز ظاهر می شوند .

[IMG]http://www.aftab.ir/articles/science_education/basis_science/images/2364d6716bd12b721cb532dd2d34c8c0.jpg[/IMG]

امیررضاعرب
منابع :
۱) http://dictionary.laborlawtalk.com
۲) http://mathworld.wolfram.com
۳)http://mathcircle.berkeley.edu
انجمن ریاضیدانان جوان

تاریخ ارسال: 1390/01/11


نظر شما چیست؟

کد امنیتی شکل بالا در کادر زیر درج شود

برای مشاهده و استفاده از فرم می بایست جاوااسکریپت بر روی مرورگر شما فعال باشد.

 
تعبیر خواب
تعبیر با تقویم
روایتی از قول امام جعفر صادق (علیه السلام) هست که می‌فرمایند مثلاً اگر در روز یا شب اول ماه قمری خوابی را ببینید تعبیر ندارد و صحیح نیست، یا اگر  در دوم و سوم ماه خوابی را ببینید تعبیرش برعکس می‌شود و به همین ترتیب تمام روزهای ماه را فرموده‌اند و این روایت تا حدودی هم شایع شده و گسترش پیدا کرده است.
دقت کنید که چیز کمی نیست!... یعنی شما که دیشب خوابی را دیده‌اید با دانستن تاریخ دیشب، می‌توانید ادامه مطلب...
تعبیرها و اشتباه‌ها
همۀ ما در طول شب یا روز خواب‌هایی می‌بینیم که ممکن است درست و صادق بوده و معنایی را در خود داشته باشند یا اینکه بی‌معنا باشند.
علت خواب‌های بی‌معنا چیزهایی مثل ضعف یا پرخوری قبل از خواب و یا صدای محیط زمان خواب و یا حتی می‌تواند نتیجه تلقین شیطان باشد و فقط پیامبران و معصومین (علیهم السلام) هستند که تمام خواب‌هایشان درست و صادق بوده و حسابشان جدا است. حضرت امام صادق (علیه السلام) به مفضل که از ادامه مطلب...
تعبیر با کتاب
در این مقاله می‌خواهم در مورد این بنویسم که هر کسی می‌تواند بعضی از خواب‌ها را با کتاب تعبیر خواب، تعبیر کند. بنابراین اجازه دهید ابتدا تعریفی کلی و خلاصه از نحوۀ تعبیر خواب ارائه کنم.
خواب‌هایی که ما می‌بینیم یا می‌خواهند معنایی را به ما بفهمانند و یا خیر؛ حالا چرا بعضی از خواب‌ها می‌خواهند معنایی را بفهمانند ولی بعضی خیر؟... چون این سوال بحث دیگری است نمی‌خواهم دربارۀ آن صحبت کنم.
خود این خواب‌های بامعنا نیز اکثراً به صورت مثال ادامه مطلب...
مبارزه با فراموشی خواب
تحقیقات نشان داده است که همۀ افراد در طی خواب خودشان رویا می‌بینند (به جز در برخی بیماری‌های شدید روانی)، منتها خیلی‌ها آن‌ها را فراموش کرده و فکر می‌کنند که اصلاً رویایی ندیده‌اند. هر چند خیلی از این رویاها ممکن است جزء رویاهای بدون تعبیر باشند ولی به هر حال رویا بوده‌اند.
حال سوال این است که چطور خواب خود را فراموش نکنیم؟ چطور صحنه‌های خواب را خوب و روشن به یاد آوریم؟ برای رسیدن به این هدف راه‌های زیادی وجود ادامه مطلب...
دفع بلا با صدقه
احادیث و روایات و همچنین تجربیات بسیاری وجود دارد که خداوند متعال با صدقه قضا و قدر را تغییر می‌دهد. به عبارتی دیگر با صدقه می‌توان به خواست خدا از وقوع بلایا و حوادث جلوگیری کرد. زیرا خود خداوند قضا و قدر را معین کرده و فقط خود او می‌تواند آن را تغییر دهد (که یکی از عواملی که فرموده قضا و قدر را به خاطر آن تغییر می‌دهد همین صدقه دادن است). البته این یکی از آثار صدقه می‌باشد. ادامه مطلب...
رسیدن تعبیر به دیگری
این نکته را به خاطر داشته باشید که تعبیر خواب شما ممکن است به همان کسی که در خواب دیده‌اید نرسد و به شخص دیگری مربوط شود. در واقع تعبیر خواب شما کیلومترها با آن شخصی که در خواب دیده‌اید فاصله داشته باشد! تجربۀ خودم من از خواب‌هایم این بوده که در موارد خیلی خیلی خیلی کمی تعبیر خواب به همان افرادی رسیده که در خواب دیده‌ام (به طوریکه در اکثر موارد فقط یک درصد احتمال می دهم که تعبیر ادامه مطلب...
دفع بلا و گرفتاری
بعضی از خواب‌ها آینده را پیشگویی کرده و می‌گویند که بلا و مصیبت و گرفتاری در پیش است و یا اینکه عمل زشت یا گناهی را مرتکب خواهیم شد. اگر این خواب‌ها درست و اصطلاحاً صادقه باشند، در واقع از مقدرات الهی می‌گویند و چیزهایی که پیش‌بینی آن شده حتماً به وقوع می‌پیوندند.
ولی خداوند راه‌هایی را تعیین کرده که نگذارید آن بلایا به وقوع بپیوندند و در واقع مقدرات خدا تغییر کند. در اصل خود خدا مقدرات را بوجود آورده ادامه مطلب...
کلیپ و ویدیو
خال اندام تناسلی سرطانیه؟! (دکتری انتظاری)
اشخاصی که در کلیپها مشاهده می کنید تعبیرگر خواب نیستند