بخشی از مقاله
اعداد كاتالان
شايد در رياضيات گسسته با مسأله ي زير برخورد كرده باشيد:
مسأله: يك صفحه ي شطرنجي 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 داريم :
با توجه به روند مقاله،آيا مي‌توانيد تعداد راه هاي متفاوت افراز را حدس بزنيد؟ بله درست حدس زديد، تعداد روش هاي متفاوت افراز عبارت است از .
اعداد كاتالان در مسأله هاي ديگري از جمله شمارش درخت ها در نظريه گراف يا شمارش نوع خاصي از افراز هاي مجموعه هاي متناهي نيز ظاهر مي شوند .
مسأله‌ي اول - پرانتزهای بالانس
فرض کنید که n جفت پرانتز دارید و می‌خواهید از آن‌ها دسته‌بندی‌های درستی بسازید. منظور از دسته‌بندی «درست» پرانتزها این است که برای هر پرانتز باز، یک پرانتز بسته وجود داشته باشد.
برای مثال (()()) یک دسته‌بندی درست و ())()( یک دسته‌بندی نادرست از پرانتزها است.
حال، مسأله این است که برای n جفت پرانتز، چند تا دسته‌بندی درست می‌توانیم انجام دهیم!؟
شاید توضیح دقیق‌تر مسأله به این صورت باشد که:
رشته‌اي از پرانتزها را «درست» می‌گوییم که در آن رشته، تعداد پرانتزهای باز با تعداد پرانتزهای بسته برابر باشد و هم‌چنین اگر از سمت چپ رشته شروع به حرکت کنیم و به‌سمت راست آن برویم به‌ازای هر پرانتز باز عدد 1 بگذاریم و به‌ازای هر پرانتز بسته عدد 1- بگذاریم در انتهایِ پیمودن رشته، جمع این اعداد «نامنفی» شود.
مسأله‌ي دوم - مثلث‌بندیِ چندضلعی‌ها
اگر تعداد راه‌های مثلث‌بندی کردن یک n+2 ضلعی منتظم را بشماریم دوباره به «اعداد کاتالان» دست می‌یابیم.
ياداوري - منظور از مثلث‌بندی کردن یک چند ضلعی منتظم، تقسیم آن چندضلعی به‌نواحی مثلثی شکل است.
در شکل ذيل مثلث‌بندی کردن 3، 4، 5 و 6 ضلعی منتظم نشان داده شده است.
همان‌طوری که می‌بینید 1، 2، 5 و 14راه برای این کار وجود دارد. برای دوضلعی منتظم هم مثلث‌بندی به 1 راه ممکن است؛ پس می‌بینیم که برای n=0 نیز برقرار است.
مسأله‌ي سوم - درخت‌های دودویی
اعداد کاتالان هم‌چنین می‌توانند تعداد درختان دودویی ریشه‌دار با n گره داخلی (همه‌ی گره‌ها به‌جز ریشه) را بشمارند.
همان‌طور در شکل ذيل می‌بینید کلیه‌ي درخت‌های دودویی ریشه‌دار با 0، 1، 2 و 3 گره داخلی نشان داده شده است.
درخت دودویی ریشه‌دار، آرایشی از گره‌ها و یال‌هاست به‌طوری یک گره به‌خصوص وجود دارد که هیچ یالی به آن وارد نمی‌شود که به آن «ریشه» می‌گوییم و هرچه از ریشه‌ي پایین می‌آییم دو یا 1 یا صفر یال وجود خواهد داشت. گره‌های داخلی آن‌هایی هستند که به دو گره دیگر وصل باشند.
مسأله‌ي چهارم - ترتيب ضرب
فرض کنید مجموعه‌ای از n+1 عدد دارید که می‌خواهید آن‌ها را دو به دو در هم ضرب کنید؛ به این معنا که n عمل ضرب باید صورت بگیرد؛ بدون عوض کردن ترتیب خود اعداد، می‌توانید اعداد را به‌ترتیب‌های گوناگونی در هم ضرب کنید.
در این‌جا تعداد ترتیب‌های ممکن برای ضرب n بین 0 تا 4 آمده است.
برای تبدیل مثال بالا به نمادگذاری پرانتزی، این کار را انجام می دهی:
به‌جز نقطه (نشانه‌ی ضرب) و پرانتزهای بسته، همه‌چیز را پاک میکنیم و سپس به‌جای همه‌ی نقطه‌ها، «پرانتز باز» جایگزین میکنیم.
برای مثال: اگر بخواهیم این عمل را روی عبارت ذيل اعمال کنیم:
(a.(((b.c).d).e))
به این صورت عمل میکنیم که همه‌چیز به‌جز نقطه و پرانتز بسته‌ها را پاک میکنیم که عبارت به‌صورت ذيل در‌می‌آید.
..).).)).
سپس «نقطه‌ها» را با «پرانتز باز» جایگزین میکنیم. در نتیجه رشته‌ی ذيل حاصل می‌شود:
(()()())
پس می‌توان نتیجه گرفت راه‌حل این مسأله نیز «اعداد کاتالان» هستن!
از این دست مسائل - که راه‌حل آن‌ها دنباله‌ی اعداد معروفی با نام «اعداد کاتالان» می‌باشد - بسیار است.
حال باید بدانیم این دنباله از اعداد از کجا آمده‌اند!؟
به‌دست آوردن جمله‌ی عمومی این دنباله‌ی اعداد دارای پیچیدگی‌هایی است که در این زنگ تفریح به آن نمی‌پردازیم بلکه فقط به بیان فرمول صریح (جمله‌ی عمومی) «اعداد کاتالان» بسنده میکنیم.
i اُمین عدد کاتالان از رابطه‌ی ذيل به‌دست می‌آید:
