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