شاید در ریاضیات گسسته با مسأله ی زیر برخورد كرده باشید:
مسأله: یك صفحه ی شطرنجی n×n در نظر بگیرید؛ می‌خواهیم با حركت روی خطوط صفحه ی شطرنجی، از نقطه ی A در گوشه ی سمت چپ پائین صفحه، شروع كرده و به نقطه ی B در گوشه ی سمت راست بالای صفحه برسیم. شرط كار این است كه فقط می‌توانیم به سمت‌های راست و بالا حركت كنیم و هرگز نباید به بالای قطر AB برویم. به چند طریق می‌توان از A به B رسید؟....

شاید در ریاضیات گسسته با مسأله ی زیر برخورد كرده باشید:
مسأله: یك صفحه ی شطرنجی n×n در نظر بگیرید؛ می‌خواهیم با حركت روی خطوط صفحه ی شطرنجی، از نقطه ی A در گوشه ی سمت چپ پائین صفحه، شروع كرده و به نقطه ی B در گوشه ی سمت راست بالای صفحه برسیم. شرط كار این است كه فقط می‌توانیم به سمت‌های راست و بالا حركت كنیم و هرگز نباید به بالای قطر AB برویم. به چند طریق می‌توان از A به B رسید؟

طرح این مسأله، انگیزه‌ای برای معرّفی مفاهیم زیر می‌باشد.
تعریف: برای ،n امین عدد كاتالان(ریاضی دان بلژیكی) عبارت است از: .

               E.C.Catalan  

تعریف: همان‌طور كه می‌دانیم هركلمه از تعدادی حرف تشكیل شده است. اگر حرف‌های تشكیل‌دهنده ی كلمات را 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 عوض كنیم پس كلمه‌ای با 1-n تا x و 1+n تا y خواهیم داشت [چرا؟].
از طرفی اگر كلمه‌ای دلخواه به طول متشكل از 1-n تا x و 1+n تا y داشته باشیم ،اولین قطعه ی آغازی این كلمه كه تعداد y ها یكی بیش تر از تعداد x هاست در نظر بگیرید و تمامی y هایی كه بعد از این قطعه ظاهر می شوند را با xو تمامی x ها را [در صورت وجود] با y عوض كنید. كلمه‌ی حاصل یك NDW است [چرا؟] .

در واقع این روش یك تناظر یك به یك بین كلماتی به طول شامل 1-n تا x و 1+n تا y و NDWهای به طول  برقرار می‌كند. چون به تعداد كلمه ی به طول شامل 1-n تا x و 1+n تا y داریم ، پس تعداد NDW های به طول  برابر است با . امّا تعداد DWها برابر است با اختلاف تعداد كلّ كلمات و تعداد NDWها، پس :

 تعداد DWهای به طول

اكنون به مسأله‌ای كه در آغاز مقاله مطرح كردیم، برمی‌گردیم.
اگر حركت به سمت راست را با x و حركت به سمت بالا را با y نشان دهیم پس تعداد راه‌های رسیدن از A به B [با توجه به شرط مسأله]برابر است با تعداد DWهای به طول كه همانا  می‌باشد.
مسأله‌ای دیگر: به چند طریق می‌توان با n جفت پرانتز ( )؛ عبارت‌های با معنی نوشت؟
مثلاً برای 3و 2و 1=n داریم:
1=n ( ) .
2=n (( )) و ( ) ( ) .
3=n (( )) ( ) و ( ) (( )) و ( ) ( ) ( ) و ((( ))) و ( ( ) ( ) ) .
اگر به جای )، x و به جای (، y قرار دهیم آن‌گاه تعداد عبارت‌‌های با معنی با n جفت پرانتز با تعداد DWهای به طول برابر خواهد بود و این یعنی برابر است.
تاكنون حلّ سه مسأله منجر به اعداد كاتالان شده است، در ذیل توجّه شما را به دو نمونه ی دیگر جلب می‌كنیم:
الف) تعداد راه‌های مختلف پرانتز‌گذاری بین 1+n نماد ریاضی عبارت است از .
به عنوان مثال اگر a و b و c و d چهار نماد ریاضی باشند، روش‌های مختلف پرانتز‌گذاری بین آن‌ها از این قرار است:

ب) یك 2+n ضلعی محدّب در نظر بگیرید. با وصل كردن رأس‌ها، می‌توان این چند ضلعی را به مثلث‌هایی افراز كرد.
به عنوان مثال برای 3=n داریم :

با توجه به روند مقاله،‌آیا می‌توانید تعداد راه های متفاوت افراز را حدس بزنید؟ بله درست حدس زدید، تعداد روش های متفاوت افراز عبارت است از ‌ .

اعداد كاتالان در مسأله های دیگری از جمله شمارش درخت ها در نظریه گراف یا شمارش نوع خاصی از افراز های مجموعه های متناهی نیز ظاهر می شوند .

نظرات شما عزیزان:

نام :

آدرس ایمیل:

وب سایت/بلاگ :

متن پیام:

نظر خصوصی

 کد را وارد نمایید:

 

 

 

عکس شما

آپلود عکس دلخواه: