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

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

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

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

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

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

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

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

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

داخل کتاب ۶۰۰ مسئله نیست در کتاب داده ساختارها و مبانی الگوریتم ها فصل ۴ صفحه ۱۸۸ و ۱۸۹ و ۱۹۰

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

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

آخه این سوال علوم امروز بود
گزینه هاش خیلی گنده منده بودن!! و شبیه عدد کاتالان ولی خود عدد کاتالان نبود
و یه گزینه هم گفته بود نمیشه