تعداد د.د.ج های متفاوت با n گره و ارتفاع h چند تاست؟
[tex]\binom{2^h}{n - 2^h 1}[/tex]
این تست رو توی کتاب دکتر قدسی دیدم، شما اول هر چی برگ هست رو حذف کنید، حالا یه درخت پر با ارتفاع h - 1 داریم، تعداد گره هاش میشه [tex]2^h - 1[/tex]، تعداد برگاش میشه [tex]2 ^{h - 1}[/tex]و این درخت همون درخت قبلیمونه که [tex]r = n - (2 ^ h - 1)[/tex]
برگ به برگاش اضاف شده، پس تعداد درختمامون میشه [tex]\binom{2^h}{r}[/tex]
(۲۸ مرداد ۱۳۹۲ ۰۸:۲۵ ب.ظ)SnowBlind نوشته شده توسط: این تست رو توی کتاب دکتر قدسی دیدم، شما اول هر چی برگ هست رو حذف کنید، حالا یه درخت پر با ارتفاع h - 1 داریم، تعداد گره هاش میشه [tex]2^h - 1[/tex]، تعداد برگاش میشه [tex]2 ^{h - 1}[/tex]و این درخت همون درخت قبلیمونه که [tex]r = n - (2 ^ h - 1)[/tex]
برگ به برگاش اضاف شده، پس تعداد درختمامون میشه [tex]\binom{n}{r}[/tex]
ممنون از جوابتان ولی با این راه حل به مشکل برخوردم
اگر فرض کنیم n=3 , h=1 باشد(ریشه در ارتفاع صفر قرار دارد) جواب فرمول گفته شده میشه ۳ ولی با ۳ نود فقط یک درخت به ارتفاع یک میشه درست کرد (درخت کامل)
به نظرم این راه حل درست که یک درخت پر با ارتفاع h-1 درست می کنیم که همان طور که گفتید تعداد گره های مصرفی [tex]2^h - 1[/tex] است می دانیم حداکثر تعداد گره های برگ در ارتفاع h برابر [tex]2 ^h[/tex] است پس نودهای باقی مانده [tex]r = n - (2 ^ h - 1)[/tex] می تواند در این تعداد جایگاه قرار گیرد بنابراین جواب برابر جایگشت [tex]\binom{2 ^h}{r}=\binom{2 ^h}{n - (2 ^ h - 1)}[/tex] می باشد که در این صورت جواب مثالی که زدم درست میشه
اگر اشتباه می کنم لطفا توضیح بدید
(۲۸ مرداد ۱۳۹۲ ۱۰:۰۹ ب.ظ)rad.bahar نوشته شده توسط:(28 مرداد ۱۳۹۲ ۰۸:۲۵ ب.ظ)SnowBlind نوشته شده توسط: این تست رو توی کتاب دکتر قدسی دیدم، شما اول هر چی برگ هست رو حذف کنید، حالا یه درخت پر با ارتفاع h - 1 داریم، تعداد گره هاش میشه [tex]2^h - 1[/tex]، تعداد برگاش میشه [tex]2 ^{h - 1}[/tex]و این درخت همون درخت قبلیمونه که [tex]r = n - (2 ^ h - 1)[/tex]
برگ به برگاش اضاف شده، پس تعداد درختمامون میشه [tex]\binom{n}{r}[/tex]
ممنون از جوابتان ولی با این راه حل به مشکل برخوردم
اگر فرض کنیم n=3 , h=1 باشد(ریشه در ارتفاع صفر قرار دارد) جواب فرمول گفته شده میشه ۳ ولی با ۳ نود فقط یک درخت به ارتفاع یک میشه درست کرد (درخت کامل)
به نظرم این راه حل درست که یک درخت پر با ارتفاع h-1 درست می کنیم که همان طور که گفتید تعداد گره های مصرفی [tex]2^h - 1[/tex] است می دانیم حداکثر تعداد گره های برگ در ارتفاع h برابر [tex]2 ^h[/tex] است پس نودهای باقی مانده [tex]r = n - (2 ^ h - 1)[/tex] می تواند در این تعداد جایگاه قرار گیرد بنابراین جواب برابر جایگشت [tex]\binom{2 ^h}{r}=\binom{2 ^h}{n - (2 ^ h - 1)}[/tex] می باشد که در این صورت جواب مثالی که زدم درست میشه
اگر اشتباه می کنم لطفا توضیح بدید
بله، شما کاملا درست میگید، جواب درست میشه [tex]\binom{2 ^h}{r}=\binom{2 ^h}{n - (2 ^ h - 1)}[/tex]