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

شاید در ریاضیات گسسته با مسأله ی زیر برخورد کرده باشید:
مسأله: یک صفحه ی شطرنجی 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 عوض کنیم پس کلمه‌ای با ۱-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 داریم :

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

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

منابع :

۱) http://dictionary.laborlawtalk.com
۲) http://mathworld.wolfram.com
۳)http://mathcircle.berkeley.edu