להוכיח זהות קומבינטורית בעזרת משפט קיילי

שלום לכולם, אני מנסה להוכיח את הזהות הבאה:

2n^{n-3}=\sum_{m=1}^{n-1}{n-2 \choose m-1}m^{m-2}(n-m)^{n-m-2}

לא מצליח לחשוב על דרך כיצד להוכיח את הזהות הנ"ל בצורה קומבינטורית ועוד בעזרת משפט קיילי. אשמח לעזרה.

נפריד לכיוונים:

  • עבור צד ימין - נוכיח בעזרת משפט קיילי שמספר העצים הפורשים הלא מכוונים שאפשר לבנות על הצמתים 1,2,...,n בתנאי שהקשת \{1,2\} משתתפת, שווה לאגף ימין של הזהות.

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

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

\sum_{m=1}^{n-1}{n-2 \choose m-1}m^{m-2}(n-m)^{n-m-2}

עבור צד שמאל: נסמן ב-E להיות קבוצת כל הקשתות האפשריות בגרף לא-מכוון פשוט עם n צמתים. לכל קשת e\in E נסמן ב-C_{e} את מספר העצים הפורשים עם הקשת e. מטעמי סימטריה, לכל e\in E מתקיים C_{(1,2)}=C_{e} ולכן נקבל:

\sum_{e\in E}C_{e}=|E|C_{(1,2)}={n \choose 2}\cdot C_{(1,2)}

עתה, נחשב בדרך נוספת את אגף שמאל. נוכיח כי מתקיים:

\sum_{e\in E}C_{e}=n^{n-2}(n-1)\,\,\,\,\,(*)

יהי T=(V,E') עץ פורש עם n צמתים. לכל קשת e\in E', גרף T הוא עץ פורש עם הקשת e ולכן תורם 1 ל-C_{e}. מאחר ומתקיים: |E'|=n-1, נוכל להסיק כי T תורם n-1 לסכום \sum_{e\in E}C_{e}. לכן כל עץ פורש n-1 לסכום. כלומר מתקיימת הטענה (*). סה"כ קיבלנו:

{n \choose 2}\cdot C_{(1,2)}=n^{n-2}(n-1)\Leftrightarrow C_{(1,2)}=\frac{n^{n-2}(n-1)}{\frac{n!}{2!\cdot(n-2)!}}=2n^{n-3}

ומכך נובעת הזהות המבוקשת.