تو جزوه آقای یوسفی واسه ۵ تا نوشته
[tex]\bg_black 5!/2 5!/2 5=125[/tex]
درخت هاشو صفحه۲۲۷ گسسته پوران میتونید ببینید
هر حالتو چطوری شمردن؟! من که متوجه نشدم
سلام.
تعداد درخت های دودویی برچسب دار بدین صورت محاسبه میشه، که N! رو در عدد کاتالان ضرب می کنیم.
دلیل اینکه N! رو ضرب در عدد کاتالان می کنیم اینه که جایگشت N نود یا برچسب رو با N! نشون می دیم.
مثلا برای N = 3 باشه، تعداد جایگشت N! = 6 خواهد بود؛ و همچنین عدد کاتالان برای N=3 برابر هست با ۵/
پس در کل تعداد درخت های برچسب دار به ازای N=3 میشه ۶*۵ = ۳۰ .
یا مثلا همون N=5 شما رو در نظر بگیریم:
۵! = ۱۲۰ حالا باید این عدد ۱۲۰ رو در عدد کاتالان به ازای N=5 ضرب کنیم.یعنی به عبارتی باید ۱۲۰*۴۲ بشه که نتیجه برابر هست با ۵۰۴۰ .
موفق باشید.
سلام. منظور سوال درختهای سادست نه جهتدار. درجه رئوس گراف رو مینویسم و تعداد حالات هرکدومشون رو. درخت رو خودتون رسم کنید:
۱- ۴ ۱ ۱ ۱
۵ حالت.
۲- ۲ ۲ ۲ ۱ ۱
۶۰ حالت.
۳- ۳ ۲ ۱ ۱ ۱
۶۰ حالت.
(۱۷ آذر ۱۳۹۱ ۱۲:۳۹ ق.ظ)azad_ahmadi نوشته شده توسط: سلام.
تعداد درخت های دودویی برچسب دار بدین صورت محاسبه میشه، که N! رو در عدد کاتالان ضرب می کنیم.
دلیل اینکه N! رو ضرب در عدد کاتالان می کنیم اینه که جایگشت N نود یا برچسب رو با N! نشون می دیم.
مثلا برای N = 3 باشه، تعداد جایگشت N! = 6 خواهد بود؛ و همچنین عدد کاتالان برای N=3 برابر هست با ۵/
پس در کل تعداد درخت های برچسب دار به ازای N=3 میشه ۶*۵ = ۳۰ .
یا مثلا همون N=5 شما رو در نظر بگیریم:
۵! = ۱۲۰ حالا باید این عدد ۱۲۰ رو در عدد کاتالان به ازای N=5 ضرب کنیم.یعنی به عبارتی باید ۱۲۰*۴۲ بشه که نتیجه برابر هست با ۵۰۴۰ .
موفق باشید.
ممنون از پاسختون ولی سوال که نگفته تعداد درخت های دودویی!
(۱۸ آذر ۱۳۹۱ ۰۳:۳۹ ق.ظ)Jooybari نوشته شده توسط: سلام. منظور سوال درختهای سادست نه جهتدار. درجه رئوس گراف رو مینویسم و تعداد حالات هرکدومشون رو. درخت رو خودتون رسم کنید:
۱- ۴ ۱ ۱ ۱
۵ حالت.
۲- ۲ ۲ ۲ ۱ ۱
۶۰ حالت.
۳- ۳ ۲ ۱ ۱ ۱
۶۰ حالت.
مشکل من تو شمارش تعداد حالات ۲و ۳ هستش. چرا جایگشت خطی شون نصف میشه؟
فرض کنید تعداد حالات تشکیل یک صف رو میشمریم. ولی برامون فرق نمیکنه کدوم طرف رو سر صف انتخاب کنیم. به عبارتی حالات abcde و edcba یکی هستن.
توی گزینه ۳ هم یه راس از درجه ۲ داریم. یک طرفش راس درجه ۳ و یک طرفش راس درجه ۱ هست. از اون راس درجه ۱ برای نامگذاری شروع میکنیم. ۵ حالت داره. راس درجه ۲ چهار حالت داره. راس درجه ۳ هم سه حالت داره. دو راس باقی مونده مشابه هم هستن. پس حالت ها بیشتر نمیشن.
n به توان
n-2
labeled trees with n nodes
وجود دارد
این سوال جالبیه
تعداد درخت های برچسب دار طبق گفته اساتید میشه همون تعداد درخت پوشا
که هردو فرمولشون میشه
[tex]n^{n-2}[/tex]