اعداد كاتالان

شايد در رياضيات گسسته با مسأله ي زير برخورد كرده باشيد:
مسأله: يك صفحه ي شطرنجي 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 داريم :

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

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

منابع :

1) http://dictionary.laborlawtalk.com
2) http://mathworld.wolfram.com
3)http://mathcircle.berkeley.edu