شمردن تعداد درخت ها ==================== شمردن تعداد درخت های :math:`n` راسی یکی از مسائل بسیار جذاب ترکیبیات هستند و راه های متنوع و خلاقانه ای برای آن وجود دارد. در این قسمت موضوع بحث درخت هایی با راس های برچسب دار هستند. (می توانید آنها را به صورت تعداد زیردرخت های فراگیر گراف :math:`K_n` در نظر بگیرید). در واقع به چندین روش اثبات خواهیم کرد که تعداد درخت های :math:`n` راسی برابر با :math:`n^{n-2}` است. قبل از خواندن راه حل هر بخش راهنمایی ها را بخوانید و سعی کنید خودتان راه حلی ارائه دهید. شمردن با دنباله درجه ای ------------------------- راهنمایی ~~~~~~~~~~~~~~~~ رابطه ای ارائه دهید که تعداد درخت های با دنباله درجه ای :math:`d_1, d_2, ..., d_n` را بشمارد. برای اثبات این رابطه به صورت استقرایی برگ حذف می کنیم! حل ~~~~~~~~~~ رابطه مورد نظر برابر است با :math:`\frac {(n-2)!} {(d_1-1)! \times (d_2-1)! \times ... (d_n-1)!}` . توجه کنید که :math:`\sum d_i-1` برابر با همان :math:`n-2` است پس عبارت بالا در واقع یک ترکیب با تکرار است! برای اثبات رابطه از استقرا روی :math:`n` استفاده کنید. به عنوان پایه در نظر داشته باشید که به ازای :math:`n \leq 2` رابطه برقرار است. حالا کافیست تنها یک برگ خاص را در نظر بگیرید (راسی مثل :math:`u` که :math:`d_u = 1` است). سپس حالت بندی کنید که تنها مجاور این راس چه راسی باشد.‌ اگر تنها مجاور راس :math:`u` راس :math:`v` باشد (توجه کنید چون :math:`n > 2` می توان نتیجه گرفت :math:`v` نباید برگ باشد) آنگاه تعداد درخت های ممکن در این حالت برابر است با :math:`\frac {(n-2)!} {(d_1-1)! \times (d_2-1)! \times ... (d_v-2)! (d_n-1)!}` . همانطور که گفتیم عبارت بالا شبیه به یک ترکیب با تکرار است. طبق اتحاد تعمیم اتحاد پاسکال جمع عبارات (بعد از حالت بندی ها) برابر با :math:`\frac {(n-2)!} {(d_1-1)! \times (d_2-1)! \times ... (d_n-1)!}` خواهد شد. همانطور که می خواستیم. حالا توجه کنید که عبارت بالا در واقع تعداد رشته های متفاوتی را می شمارد که از حرف :math:`i` به تعداد :math:`d_i-1` بار در آن آمده است. پس مثل این است که هر درخت را به یک دنباله :math:`n-2` تایی از اعداد :math:`1` تا :math:`n` نسبت دادیم. پس اگر به ازای همه :math:`d_1,d_2,...,d_n` های ممکن عبارت را جمع کنیم حاصل برابر با :math:`n^{n-2}` خواهد شد که تعداد کل درخت های متفاوت :math:`n` راسی است. کد پروفر ---------------- راهنمایی ~~~~~~~~~~~~~~~~~ تناظری یک به یک از درخت های :math:`n` راسی به دنباله های :math:`n-2` تایی از اعداد :math:`1` تا :math:`n` ایجاد می کنیم. حل ~~~~~~~~~~~ تابع تناظر ما به اینصورت عمل می کند که در ابتدا درخت :math:`T` را در نظر می گیریم و تا زمانی که تعداد راس های آن بیشتر از 2 است هر بار برگ :math:`u` که برچسب آن کمینه است را حذف می کنیم. سپس برچسب تنها راس مجاور :math:`u` را در روی کاغذ می نویسیم. در انتها :math:`n-2` عددی که روی کاغذ نوشتیم را به ترتیب نوشتن در نظر بگیرید. آن ها دنباله :math:`n-2` ما را تشکیل می دهند. برای اثبات یک به یک بودن تناظر باید ثابت کنیم هر دنباله :math:`n-2` تایی از اعداد :math:`1` تا :math:`n` به صورت یکتایی به درخت های :math:`n` راسی متناظر شده اند. دنباله :math:`s_1,s_2,...,s_{n-2}` را در نظر بگیرید. می خواهیم درختی که به آن تناظر داده شده است را پیدا کنیم. اول از همه توجه کنید که در فرایند تناظر دادن ما راس :math:`i` دقیقا :math:`d_i-1` بار در رشته ظاهر شده است(چرا؟). پس اعدادی که در بین :math:`s_1,s_2,...,s_{n-2}` ظاهر نشده اند باید برگ های درخت باشند. در فرایند تناظر در اولین گام برگی که برچسب آن کمینه بود را حذف کردیم. پس کمترین عددی که در بین :math:`s_1,s_2,...,s_{n-2}` ظاهر نشده است را :math:`u` بنامید. ابتدا باید :math:`u` حذف شده باشد و تنها مجاور :math:`u` راس :math:`s_1` می باشد. حالا به صورت استقرایی می توان درخت متناظر با :math:`s_2,...,s_{n-2}` را به صورت یافت. سپس یال بین :math:`u,s_1` را به درخت اضافه می کنیم و درخت متناظر با :math:`s_1,s_2,...,s_{n-2}` به دست خواهد آمد. تناظر به گراف تابعی ------------------ راهنمایی ~~~~~~~~~~~~~~~~~~~~~~~ درخت دو رنگ را درختی تعریف می کنیم که راس :math:`A` در آن به رنگ آبی در آمده و رنگ :math:`B` به رنگ قرمز (حتی ممکن است :math:`A, B` یک راس باشند). واضح است که به ازای هر درخت :math:`n` راسی دقیقا :math:`n^2` درخت دورنگ داریم پس اگر :math:`c` تا درخت :math:`n` راسی داشته باشیم آنگاه :math:`c \times n^2` تا درخت دورنگ :math:`n` راسی داریم. در این قسمت تناظری یک به یک بین گراف های تابعی :math:`n` راسی (که تعداد آن ها :math:`n^n` تا است) و درخت های دو رنگ ایجاد می کنیم. حل ~~~~~~~~~~~~~ گراف تابعی را در نظر بگیرید. همانطور که می دانید در هر گراف تابعی از هر مولفه همبندی (در گراف زمینه) از یک دور جهت دار تشکیل شده است که از هر راس آن یک درخت آویزان است. شهودا برای تبدیل این گراف تابعی به درخت کافیست یک یال از هر دور را حذف کنیم سپس مولفه های همبندی گراف تابعی را به هم وصل کنیم تا تبدیل به درخت شود اما باید طوری این فرایند را انجام دهیم که تناظر یک به یک باشد و بتوان از روی درخت دو رنگ فهمید کدام یال حذف شده است! فرض کنید به ازای هر مولفه همبندی گراف تابعی (در گراف زمینه) کمترین برچسب در دور آن را زیبایی مولفه می نامیم و راسی که این برچسب کمینه را دارد راس زیبای مولفه بنامید. حالا برای تناظر فرایند زیر را انجام دهید. - مولفه ها طوری چپ به راس مرتب کنید که زیبایی مولفه ها از چپ به راست **نزولی** باشد. - در هر کدام از مولفه ها فرض کنید دور آن :math:`p_1,p_2,...,p_k` باشد به طوریکه :math:`p_1` راس زیبای مولفه باشد. ابتدا یال :math:`p_kp_1` را حذف کنید. سپس :math:`p_k` را به راس زیبای مولفه بعدی (در سمت راست) وصل کنید. - راس :math:`p_1` در چپ ترین مولفه را آبی کنید و راس :math:`p_k` در راست ترین مولفه را قرمز کنید. سپس جهت دهی یال ها را از بین ببرید. به این صورت از گراف تابعی که داشتیم یک درخت دو رنگ ساختیم. چرا زیبایی مولفه را **کوچکترین** راس دور تعریف کردیم و چرا مولفه ها را طوری مرتب کردیم که زیبایی ها **نزولی** باشد؟ دلیل این کار تنها این بود که مسیر راس آبی به قرمز این ویژگی را داشته باشد که به آن ویژگی جذاب می گوییم. **ویژگی جذاب** : ابتدا توجه کنید که هر کدام از دور های گراف تابعی در واقع الان یک بازه از مسیر بین راس آبی و قرمز هستند. از راس آبی شروع کنید و به سمت راس قرمز بروید و برچسب ها را نگاه کنید. فرض کنید الان روی راس :math:`u` هستیم و کمترین برچسبی که قبل از :math:`u` در طول مسیر دیده ایم :math:`X` باشد. اگر :math:`u