(۱۶ بهمن ۱۳۹۳ ۰۵:۴۹ ب.ظ)LunaM نوشته شده توسط:  می خواهیم تعداد درخت های دودوی متفاوت را که با n گره می توان ساخت بدست آوریم.فرض کنید که گره های هرکدام از این درخت ها را به روش میان ترتیب از ۱ تا n شماره گذاری می کنیم.با این شماره گذاری ، فرض کنید شماره [tex]1\: <=\: i\: <=n[/tex] ریشه درخت باشد. در آن صورت زیر درخت راست آن حتماً باید n-i گره داشته باشد.
حال اگر [tex]T(n)[/tex] تعداد درخت دودیی با n گره باشد ، تعداد زیر درخت های چپ و راست ریشه به ترتیب برابر [tex]T(i-1)[/tex] و [tex]T(n-i)[/tex] خواهند بود.
در آن صورت اگر گره ی i ریشه باشد ، حاصل ضرب [tex]T(i)T(n-i)[/tex] برابر تعداد کل درخت هاست.
برای در نظر گرفتن همه حالات یک رابطه بازگشتی بدست می آید. که جواب آن عدد کاتلان است:
[tex]T(n)=\frac{1}{n 1}C(2n,n)[/tex]

به نقل از کتاب دکتر قدسی

(۱۶ بهمن ۱۳۹۳ ۰۶:۰۴ ب.ظ)pooyaa نوشته شده توسط:  

(16 بهمن ۱۳۹۳ ۰۵:۴۹ ب.ظ)LunaM نوشته شده توسط:  می خواهیم تعداد درخت های دودوی متفاوت را که با n گره می توان ساخت بدست آوریم.فرض کنید که گره های هرکدام از این درخت ها را به روش میان ترتیب از ۱ تا n شماره گذاری می کنیم.با این شماره گذاری ، فرض کنید شماره [tex]1\: <=\: i\: <=n[/tex] ریشه درخت باشد. در آن صورت زیر درخت راست آن حتماً باید n-i گره داشته باشد.
حال اگر [tex]T(n)[/tex] تعداد درخت دودیی با n گره باشد ، تعداد زیر درخت های چپ و راست ریشه به ترتیب برابر [tex]T(i-1)[/tex] و [tex]T(n-i)[/tex] خواهند بود.
در آن صورت اگر گره ی i ریشه باشد ، حاصل ضرب [tex]T(i)T(n-i)[/tex] برابر تعداد کل درخت هاست.
برای در نظر گرفتن همه حالات یک رابطه بازگشتی بدست می آید. که جواب آن عدد کاتلان است:
[tex]T(n)=\frac{1}{n 1}C(2n,n)[/tex]

به نقل از کتاب دکتر قدسی

کجای ۶۰۰نوشته؟میشه لطفا شماره صفحه بدید

(۱۶ بهمن ۱۳۹۳ ۰۵:۴۹ ب.ظ)LunaM نوشته شده توسط:  می خواهیم تعداد درخت های دودوی متفاوت را که با n گره می توان ساخت بدست آوریم.فرض کنید که گره های هرکدام از این درخت ها را به روش میان ترتیب از ۱ تا n شماره گذاری می کنیم.با این شماره گذاری ، فرض کنید شماره [tex]1\: <=\: i\: <=n[/tex] ریشه درخت باشد. در آن صورت زیر درخت راست آن حتماً باید n-i گره داشته باشد.
حال اگر [tex]T(n)[/tex] تعداد درخت دودیی با n گره باشد ، تعداد زیر درخت های چپ و راست ریشه به ترتیب برابر [tex]T(i-1)[/tex] و [tex]T(n-i)[/tex] خواهند بود.
در آن صورت اگر گره ی i ریشه باشد ، حاصل ضرب [tex]T(i)T(n-i)[/tex] برابر تعداد کل درخت هاست.
برای در نظر گرفتن همه حالات یک رابطه بازگشتی بدست می آید. که جواب آن عدد کاتلان است:
[tex]T(n)=\frac{1}{n 1}C(2n,n)[/tex]

به نقل از کتاب دکتر قدسی