اعداد کاتالان کجا رخ می دهند؟
-تعداد psp با تعداد معینی از جفت براکت
-تعداد درختان دوتایی با تعداد برگ معین
-تعداد مسیرهایی از گوشه سمت چپ پایین تا گوشه سمت راست بالا در مربع n * n که با مورب تماس ندارند
-تعداد تقسیمات n-gon به مثلث
چگونه شمارش کنیم؟1) فرمول شماره n کاتالان:
2)
•بیایید یک PSS با طول 2n
داشته باشیم
•بدیهی است که با یک مهاربند باز شروع می شود
•بنابراین، بگویید P = (A)B، جایی که A و B – همچنین psp (علاوه بر این، A و B می توانند خالی باشند)
•اگر طول A = 2k باشد، می توان دنباله A را به روش های Ck ترکیب کرد
•سپس طول B = 2(n – k - 1) و B را می توان به روش های Cn-k-1 ترکیب کرد
•فرمول dp را می بینیم: Cn = مجموع (Ck * Cn-k-1) برای همه k <
مواد استفاده شده: