اعداد کاتالان
اعداد کاتالان در ریاضیات ترکیبی، یک سری از اعداد طبیعی هستند که در مسائل شمارشی متنوع که معمولاً اشیا به صورت بازگشتی تعریف شده را در بر می‌گیرند، رخ می‌دهند. این اعداد به افتخار ریاضیدان بلژیکی شارل کاتالان (۱۸۹۴-۱۸۱۴) اعداد کاتالان نامیده می‌شوند. وی استنتاج مقدماتی از فرمول را کشف کرد. کاتالان مقالات متعددی در زمینه آنالیز، ترکیبیات، جبر، هندسه، احتمالات و نظریه اعداد منتشر کرد. درستی حدس او که اعداد ۰، ۱، ۸، ۹ تنها زوج اعداد کامل متوالی است که به صورت توانی می‌باشد در دهه ۱۹۷۰ ثابت شد.
nاُمین عدد کاتالان عبارت است از:
formula_1
چند عدد اولیه کاتالان عبارتند از:
یک عبارت دیگر برای formula_2 به صورت زیر است: formula_3 عبارت فوق نشان می‌دهد کهformula_2 یک عدد طبیعی است که این نتیجه از فرمول اول چندان بدیهی نبود. این عبارت اساس اثبات آندره در مورد صحت فرمول را تشکیل می‌دهد. هم چنین اعداد کاتالان از رابطه بازگشتی زیر نیز به دست می‌آیند:
formula_5
و همچنین: formula_6
که می‌تواند برای محاسبه آن‌ها کاراتر باشد.
به‌طور مجانبی اعداد کاتالان به صورت formula_7 رشد می‌کنند که نشان می‌دهد که عبارت سمت راست برای ∞ →n به سمت یک میل می‌کند.(این عبارت می‌تواند با استفاده از تقریب استرلینگ برای !n اثبات شود) تنها اعدادی از دنباله کاتالان فرد هستند که به صورت formula_8 هستند. بقیه همگی زوج می‌باشند.
تعداد زیادی از مسائل شمارشی در ترکیبیات هستند که راه حلی با استفاده از اعداد کاتالان برای آن‌ها ارائه شده‌است. کتاب ترکیبیات شمارشی جلد دوم اثر ریچارد استانلی شامل مجموعه‌ای از تمرین هاست که ۶۶ تفسیر مختلف از اعداد کاتالان را شرح می‌دهد. در زیر چند نمونه آمده‌است .
- formula_2 تعداد کلمات Dyck به طول ۲n است. یک کلمه Dyck یک رشته است که n تاX و n تا Y دارد؛ به گونه‌ای که تعداد Yها در هر بخش آغازین آن بیشتر از تعداد Xهاست. برای مثال در زیر کلمات Dyck با طول ۶ آمده اند:
XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY
- چنانچه هر نماد X را به صورت یک پرانتز باز ببینیم و هر نماد Y را یک پرانتز بسته آنگاهformula_2 تعداد عباراتی که شامل n جفت پرانتزگذاری صحیح هستند را نشان می‌دهد.
- formula_2 تعداد راه‌های مختلفی است که n+۱ عامل می‌توانند پرانتزگذاری شوند. برای n=۳ به عنوان مثال ۵ پرانتزگذاری مختلف برای چهار عامل را داریم:
formula_12
- formula_2تعداد درخت‌های دودویی غیر هم ریخت با n راس است که بچه دارند که معمولاً رئوس داخلی یا شاخه گفته می‌شوند.
- formula_2 تعداد راه‌های مختلفی است که یک چندضلعی محدب با n+۲ ضلع می‌تواند با وصل کردن رأس‌ها با خطوط مستقیم مثلث بندی شود. شش گوشه زیر برای n=۴ نشان می‌دهد:
چندین راه برای نشان دادن اینکه چرا فرمول formula_15 مسائل ترکیبیاتی ذکر شده را حل می‌کند وجود دارد. اولین اثبات از تابع مولد استفاده می‌کند. دومین و سومین اثبات مثال‌هایی از اثبات نگاشت‌های دوطرفه هستند.
می بینیم که تعداد زیادی از مسائل ترکیبیاتی فوق از راه بازگشتی حل می‌شوند.
با استفاده از فرمول formula_5 می‌توانیم با استفاده از تکنیک‌های شناخته شده برای توابع مولد یک فرمول واضح برای اعداد کاتالان به دست بیاوریم. با تعریف formula_17 که همه اعداد کاتالان را شامل می‌شود شروع می کنیم: formula_18
اگر (f(z را در خودش ضرب کنیم و formula_19 را به دست بیاوریم، نخستین جملات این چنین هستند:
...+formula_20
ضرایب برای توان‌های z همانهایی هستند که از معادله formula_15 بر می‌آید
...+formula_22
اگر که (f(z رادر z ضرب کنیم و به آن formula_23 را بیفزاییم به دست می آوریم:
formula_24
معادله فوق یک معادله درجه دو است که می‌توانیم ان را حل کنیم. آن را به صورت formula_25 می نویسیم. بنابراین به دست می آوریم:
formula_26
توجه کنید که ما علامت منفی را برگزیدیم. چون میدانیم کهformula_27؛ بنابراین اگر علامت مثبت را جایگذاری کنیم وقتی z→0، آنگاه formula_28
برای بسط از فرمول دوجمله‌ای استفاده می‌کنیم؛ اگر که با استفاده از فرمول دوجمله‌ای با نماهای اعشاری آشنا نیستید، نگران نباشید. دقیقاً همانگونه است؛ با این تفاوت که هیچگاه تمام نمی‌شود. بیایید به فرمول دوجمله‌ای برای یک نمای صحیح نگاهی بیندازیم و همان محاسبات را برای یک عدد اعشاری انجام دهیم. اگر n یک عدد صحیح باشد، فرمول دوجمله‌ای به این قرار است:
...formula_29
اگرn یک عدد صحیح باشد، صورت کسر سرانجام یک عبارت به صورت (n-n)خواهد داشت؛ بنابراین آن جمله و تمام جملات بعد ازآن صفر خواهند بود. اگر nعدد صحیح نباشد و مثلاً برای مثال ما formula_30 باشد، صورت کسر صفر را خواهد گذراند و ادامه خواهد یافت. در زیر تعدادی از نخستین جملات بسط آمده اند:
formula_31
و به دست می آوریم:
formula_32
از معادله 8 و 9 داریم:
formula_33
عباراتی نظیر 7.5.3.1 کمی دردسرسازند. این عبارات شبیه فاکتوریل‌ها هستند؛ اما اعداد زوج را در برندارند. اما توجه کنید که formula_34 و formula_35 و formula_36 و مشابه این. بنابراین formula_37 . بنابراین اگر این ایده را برای معادله 10 به کار ببریم به دست می آوریم:
formula_38
از این عبارت می‌توانیم نتیجه بگیریم که n امین عدد کاتالان با این فرمول به دست می‌آید:
formula_39
ماتریس nn هانکل که هر درایه formula_40 آن عدد کاتالان formula_41 است بدون توجه به n دترمینانی برابر یک دارد. برای مثال برای n=۴ داریم: توجه کنید که درایه‌ها شیفت خورده‌اند و به صورت formula_42 بازهم بدون توجه به n دترمینان یک است. برای مثال برای n=۴ داریم:
دنباله کاتالان نخستین بار در قرن هیجدهم توسط لئونارد اویلر به کار برده شد که به تعداد راه‌های تقسیم کردن یک چندضلعی به مثلث علاقه‌مند بود. شارل کاتالان ارتباط بین پرانتزگذاری عبارات را در طول کشفیاتش در باره معمای برج‌های هانوی کشف کرد. ترفند شمارشی برای کلمات Dyck نیز توسط د.آندره در سال ۱۸۸۷ به دست آمد.
بررسی روش‌های برنامه‌نویسی اعداد کاتالان
ویکی‌پدیای انگلیسی
اعداد کاتالان