فرم بازگشتی اعداد کاتالان چطوری اثبات میشه؟تو کدوم صفحه گریمالدی هست؟
[tex]C_{n}=\sum_{k=1}^{n}C_{k-1}.C_{n-k}[/tex]
آیا فرم دیگه ای هم داره؟
تو فصل حل روابط بازگشتی گریمالدی اثبات این فرمول اومده.(دقیقا صفحه ۴۸۸ از PDF زبان اصلیش)
راه حلش رو نمیدونم توی گریمالدی هست یا نه ولی توی بعضی کتابا یه مثال هست که جوابش همون عدد کاتالان میشه:
رئوس یک ۲n ضلعی منتظم رو به چند طریق میشه دوبه دو به هم وصل کرد که این پاره خط‌ها همدیگر رو قطع نکنن.
جواب: برای n=1 یک راه و برای n=2 دو راه داریم. برای n های بزرگ میشه یه یال رو وصل کرد؛ مساماً رئوس سمت راست به هم و رئوس سمت چپ به هم وصل میشن و جوابشون درهم ضرب میشه. اگه سمت چپ یال اولیمون ۲n-2k راس باشه، سمت چپ ۲k-2 راس داریم. مقدار k هم از ۱ تا n تغییر میکنه.
اثباتش با تابع مولد هست و پیچیده اما توضیحات زیر در موردش هست
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
من بعد از این پستم پاسخهای دوستان رو دیدم.بهرحال تا الان دنبالش بودم که به مطالب بالا رسیدم.از دوستان هم ممنونم بابت پاسخ
(۱۷ دى ۱۳۹۰ ۰۱:۵۸ ب.ظ)mfXpert نوشته شده توسط: تو فصل حل روابط بازگشتی گریمالدی اثبات این فرمول اومده.(دقیقا صفحه ۴۸۸ از PDF زبان اصلیش)کتاب شما چاپ پنجمه؟ چون تو کتاب من تو این صفحه نیست.
(۱۷ دى ۱۳۹۰ ۰۳:۱۲ ب.ظ)Fardad-A نوشته شده توسط: کتاب شما چاپ پنجمه؟ چون تو کتاب من تو این صفحه نیست.برا من چاپ پنجمه.اولین مثال از بخش ۱۰/۵ که می خواد یه فرمول برای تعداد درخت های دودویی ممکن که میشه با n گره ساخت رو به دست بیاره.تو این مثال فرمول رو اثبات می کنه
سلام دوستان چرا در کتاب الگوریتم مقسمی جمله n+1ام کاتالان رو گفته این می شه مگه این جمله nام نمی شه
[tex]\frac{1}{n 1}\binom{2n}{n}[/tex]
این میشه جمله n+ 1 ام و صحیح است