تعداد درختان دودویی

[hadi e]

با سلام به همه ی دوستان عزیز
سوالی توی زمینه ی گراف ها و درختان دودویی داشتم که چند روز هر کاری دارم میکنم جواب نمیگیرم
این سوال رو استادمون مطرح کرد که البته لازم به ذکره خودش هم نتونست جواب درست و قانع کننده ای رو بدست بیاره این سوال تستی بود و من هم گزینه هاش رو مطرح میکنم
سوال : با 5 گره چند درخت دودویی متفاوت با عمق5 میشه درست کرد؟
دوستان ریشه رو توی سطح 1 در نظر بگیرید.
خب حالا گزینه هاش : گزینه اول 50 گزینه ی دوم 32 گزینه ی سوم 31 و گزینه ی چهارم 60
البته دوستان توجه کنند که درختان حتما باید دودویی باشند
البته من خودم با توجه به عدد کاتالان که تعداد کل درختان دودویی رو بدست میاره میشه دو تا گزینه رو حذف کرد چون عدد کاتالان این مسئله رو میشه 42 که دو تا گزینه رو حذف کرد و فقط میمونه دو تا گزینه ی 31 و 32 که میتونه جوابمون باشه البته دوستان زیاد روی گزینه ها حساس نباشید چون ممکنه اصلا گزینه ها اشتباه باشند
شما فقط با یه فرمول درست و استدلال درست این مسئله رو حل کنید

[hadi e]

البته دوستان من خودم با یک استدلال حلش کردم که متاسفانه جوابی که گرفتم توی گزینه ها نبود به همین خاطر استاد نپذیرفت
ببینید وقتی ما میگیم که درخت دودویی با عمق ق 5 با 5 گره یعنی درختمون مجبوره که توی هر سطح فقط یک گره داشته باشه
پس به غیر از ریشه که فقط میتونه یک حالت داشته باشه بقیه ی گره ها میتونند هم گره ی سمت چپ داشته باشند و هم گره ی سمت راست پس با توجه به عمل ضرب میشه چهار گره که هر کدوم دو حالت داره پس 2*2*2*2 که جواب میشه 16

[hadi e]

دوستان کسی در مورد این سوال نظری نداره؟
چطوری حل میشه و با چه روش و استدلالی؟
منتظرم ؟؟/

[hadi e]

دوستان این سوال رو هم آخرش بعد از کلی بالا و پایین کردن حلش کردم جواب درستش میشه همون 16 و با همون روش بالا استدلالش کردم و حلش کردم و اثبات هم شد