מציאת בעיה קומבינטורית לנוסחה

שלום לכולם, אשמח לקבל עזרה עם התרגיל הבא:

תנו הוכחה קומבינטורית מלאה לנוסחה הבאה - לכל k\geq 2 מתקיים:

k=\sum_{i=0}^{n-1}(-1)^{i}{n-1 \choose i}k^{n-i}(k-1)^{i}

אני לא מצליח לחשוב על בעיה שמתאימה לנוסחה. חשבתי לנסות לבנות בעיה שקשורה לווקטורים אבל ללא הצלחה.

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

בעיה קומבינטורית - מספר הוקטורים בעלי אורך n מעל א"ב המכיל k אותיות שבהם במקומות \{1,...,n-1\} מופיעה הספרה 1.

תחילה, נוכיח את צד שמאל של המשוואה - בכל ה- (n-1) המקומות הראשונים, מופיעה הספרה 1 ובמקום ה-n יש לנו k אפשרויות לבחירה של האות. לכן מספר הוקטורים הוא k.

עתה, נוכיח את צד ימין של המשוואה - נפתור ע"פ עקרון הכלה והפרדה:
עולם: כל הוקטורים בעלי אורך n מעל א"ב המכיל k אותיות.

תכונות: יש n-1 תכונות כאשר התכונה ה-P_{i} היא שבמקום ה-i לא מופיעה הספרה 1.

יעד: מאחר ומדובר בתכונות הרעות, עלינו למצוא את E(0).
קודם כל, נשים לב כי מספר הוקטורים בעלי אורך n מעל א"ב המכיל k אותיות הוא:

W(0)=k^{n}

עתה, נשים לב כי אם במקום ה-i לא מופיעה הספרה 1, אזי נוכל להסיק כי במקום זה ישר k-1 אפשרויות לבחירת אות ובשאר ה-n-1 המקומות יש k אפשרויות, כך שבסה"כ נקבל:

W(P_{i})=(k-1)\cdot k^{n-1}\Longrightarrow W(1)={n-1 \choose 1}k^{n-1}(k-1)

אם במקום ה-i וגם מקום ה-j לא מופיעה הספרה 1, אזי נוכל להסיק כי במקומות אלה יש k-1 אפשרויות לבחירת אות ובשאר ה- n-2 המקומות יש k אפשרויות, כך שסה"כ נקבל:

W(P_{i},P_{j})=(k-1)^{2} \cdot k^{n-2} \Longrightarrow W(2)={n-1 \choose 2}k^{n-2}(k-1)^{2}

ע"פ הסימטריות, לכל i תכונות נקבל:

W(i)={n-1 \choose i}k^{n-i}(k-1)^{i} \Longrightarrow E(0)= \sum_{i=0}^{n-1}(-1)^{i}{n-1 \choose i}k^{n-i}(k-1)^{i}

מקווה שהפתרון מובן.

לייק 1