כמה עצים פורשים שבהם n הצמתים הראשונים בלבד הם עלים?

שלום לכולם,
כמה עצים לא מכוונים פורשים 2n צמתים שבהם n הצמתים הראשונים בלבד הם עלים (והיתר אינם עלים)?
תודה רבה על העזרה.

כששואלים שאלה בפורום, נהוג להסביר איפה נתקעת ומה ניסית לעשות. השאלה הנ"ל כמעט זהה לשאלה הקודמת ששאלת ועזרו לך איתה. להבא, אנא נסה להסביר בדיוק מה ניסית לעשות ואיפה נתקעת, אחרת אנשים יאבדו עניין לעזור לך.

בדיוק כמו בשאלה הקודמת ששאלת, קיימת בייקציה בין קבוצת העצים הלא מכוונים המורכבים מ-n צמתים שונים לבין קבוצת המילים (הנקראים פרופר) באורך n-2 מעל האפלבית \{1,\ldots,n\}. הצמתים יופיעו במילת הפרופר כדרגתם פחות 1. אולם בשונה מהתרגיל הקודם, עלינו להשתמש בעקרון ההכלה והפרדה על מנת למצוא את מספר העצים הלא מכוונים אשר פורשים 2n צמתים שונים בהם יש בדיוק n עלים.

נפתור בעזרת עקרון הכלה והפרדה:
עולם: כל העצים הפורשים הלא מכוונים עם 2n צמתים. ע"פ משפט קיילי נקבל:

W(0)=2n^{2n-2}

תכונות: יהיו 2n תכונות כאשר משמעות תכונה p_{i} היא שהצומת ה-1\leq i\leq 2n הוא עלה.
יעד: עלינו למצוא את E(n).
נניח כי r תכונות מתקיימות ולכן יש r עלים. כלומר יש 2n-r אותיות אשר יכולות להופיע במילת הפרופר המתאימה. לכל מקום יש 2n-r אפשרויות ויש 2n-2 מקומות ולכן נקבל:

W(p_{1},...,p_{r})=(2n-r)^{2n-2}\Rightarrow W(r)={2n \choose r}\cdot(2n-r)^{2n-2}

סה"כ נקבל:

E(n)=\sum_{r=n}^{2n}(-1)^{r-n}\cdot{r \choose n}\cdot W(r)=\sum_{r=n}^{2n}(-1)^{r-n}\cdot{r \choose n}\cdot{2n \choose r}\cdot(2n-r)^{2n-2}