این سوال را میتوان به سوالی دیگر تغییر داد:به چند طریق میتوان اعداد 1 تا یازده را روی دانه ها چید طوری که عدد هر فرزند از عدد پدرش کمتر باشد که در آن عدد هر انگور شماره خورده شدن آن است.یعنی اول دانه انگور شماره یک خورده میشود،سپس دانه انگور شماره دو خورده میشود و به همین ترتیب پیش میرویم.به این ترتیب انگوری خورده نمیشود مگر اینکه بچه هایش خورده شده باشند.حال سوال جدید را حل میکنیم:

میدانیم عدد 11 همیشه در ریشه است.حال 3 عدد از 10 عدد باقیمانده را انتخاب کرده و در خانه های a و m و n میگذاریم(ترکیب 3 از 10)که به دو حالت چیده میشوند(عدد بیشینه بین این سه همواره در a است).در سمت چپ نیز عدد بیشینه از 7 عدد باقیمانده در b قرار میگیرد.سپس 4 عدد از 6 عدد باقیمانده را برای قرارا گیری در خانه های cو d و e و f انتخاب میکنیم(ترکیب 4 از 6)که بیشینه آن ها همواره در خانه c قرار میگیرد و اعداد در خانه های d و e و f به !3 حالت چیده میشوند.دو عدد باقیمانده نیز به یک صورت در خانه های x و y قرار میگیرند.پس جمعا تعداد حالت ها برابر است با:

پس گزینه ب درست است. موفق باشید!!

رئوس رو توسط شماره گذاری DFS شماره گذاری میکنیم (مانند شکل زیر)

تعریف: $n_i$ برابر تعداد رئوس درختی به ریشه $i$ میباشد.

تعریف: $a_i$ برابر پاسخ مساله برای درختی به ریشه $i$ میباشد.

تعریف: $v_i$ مجموعه فرزندان راس $i$ میباشد.

حال $a_i$ از طریق رابطه بازگشتی زیر محاسبه میشود: $$ a_i = \frac{(n_i-1)!}{ \prod_{k \in v_i} n_k!} \times \prod_{k \in v_i} a_k$$

(اثباتش به عهده خودتون)

جوابی که بدست میاد اینه:

یعنی گزینه 2

اگر توی اثباتش مشکلی داشتید بگید اثبات کنم اما بهتره خودتون اثبات کنید