|
در این زنگ تفريح می‌خواهیم شما را با مجموعه‌ای از مسائل آشنا کنیم که کاملاً عین هم هستند یعنی راه‌حل هر يك از این مسائل، دنباله‌ای از اعداد است که به آن «اعداد کاتالان» می‌گوییم.
همان‌طور که در ادامه خواهید دید می‌توانیم فرموت صریح این اعداد را به روش‌های مختلف به‌دست آوریم!
|
مسأله‌ي اول - پرانتزهای بالانس | فرض کنید که 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 آمده است.
برای تبدیل مثال بالا به نمادگذاری پرانتزی، این کار را انجام می دهی:
به‌جز نقطه (نشانه‌ی ضرب) و پرانتزهای بسته، همه‌چیز را پاک می‌کنیم و سپس به‌جای همه‌ی نقطه‌ها، «پرانتز باز» جایگزین می‌کنیم.
برای مثال: اگر بخواهیم این عمل را روی عبارت ذيل اعمال کنیم:
به این صورت عمل می‌کنیم که همه‌چیز به‌جز نقطه و پرانتز بسته‌ها را پاک می‌کنیم که عبارت به‌صورت ذيل در‌می‌آید.
سپس «نقطه‌ها» را با «پرانتز باز» جایگزین می‌کنیم. در نتیجه رشته‌ی ذيل حاصل می‌شود:
پس می‌توان نتیجه گرفت راه‌حل این مسأله نیز «اعداد کاتالان» هستن!
از این دست مسائل - که راه‌حل آن‌ها دنباله‌ی اعداد معروفی با نام «اعداد کاتالان» می‌باشد - بسیار است.
حال باید بدانیم این دنباله از اعداد از کجا آمده‌اند!؟
به‌دست آوردن جمله‌ی عمومی این دنباله‌ی اعداد دارای پیچیدگی‌هایی است که در این زنگ تفریح به آن نمی‌پردازیم بلکه فقط به بیان فرمول صریح (جمله‌ی عمومی) «اعداد کاتالان» بسنده می‌کنیم.
i اُمین عدد کاتالان از رابطه‌ی ذيل به‌دست می‌آید:
|