משפט המולטינום

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

## נוסחת המולטינום

עבור *m* מספר טבעי ו-*n* מספר אי-שלילי (חיובי או אפס), מתקיים:
:(x_1 + x_2  + \cdots + x_m)^n 
 = \sum_{k_1+k_2+\cdots+k_m=n} {n \choose k_1, k_2, \ldots, k_m} x_1^{k_1} \cdots x_m^{k_m}\,,
כאשר
: {n \choose k_1, k_2, \ldots, k_m}
 = \frac{n!}{k_1!\, k_2! \cdots k_m!}
הוא **המקדם המולטינומי**, המהווה הכללה של המקדם הבינומי.

הסכום האמור נלקח על כל הקומבינציות האפשריות של מספרים אי-שליליים של *k*1 עד*k**m* כך שסכום כל *k*i הוא *n*. כלומר, עבור כל איבר בסכום, סכום המעריכים בחזקות חייב להסתכם ל-*n*.
(נציין כי איברים מהצורה *x*0 נלקחים בתור 1, אף אם *x* הוא 0).

עבור המקרה הפרטי *m* = 2 מתקבל הבינום של ניוטון.

את המשפט ניתן להוכיח באינדוקציה על *m*, ובעזרת הבינום של ניוטון.

### דוגמה
החזקה השלישית של הביטוי *a* + *b* + *c* נתונה על ידי:

:(a+b+c)^3 = a^3 + b^3 + c^3 + 3 a^2 b + 3 a^2 c + 3 b^2 a + 3 b^2 c + 3 c^2 a + 3 c^2 b + 6 a b c.

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

## המקדם המולטינומי בקומבינטוריקה
כאמור, המקדם   {n \choose k_1, k_2, \ldots, k_m}= \frac{n!}{k_1!\, k_2! \cdots k_m!} נקרא **המקדם המולטינומי**. למקדם זה יש משמעות קומבינטורית, המכלילה את משמעות המקדם הבינומי:  {n \choose k_1, k_2, \ldots, k_m} היא מספר הדרכים לחלק *n* עצמים שונים ל-*m* קבוצות, כך שבקבוצה הראשונה יש *k*1 עצמים, בקבוצה השנייה *k*2 עצמים וכן הלאה.

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

### דוגמה
נחשב את מספר המחרוזות השונות שאפשר להרכיב בעזרת האותיות b,a,n,a,n,a - סה"כ יש כאן 6 אותיות, מתוכן פעם אחת b, פעמיים n, ושלוש פעמים a - ולכן התשובה היא {6 \choose 3, 2, 1}=\frac{6!}{1! 2! 3!} = 60.

## זהויות מולטינומיות
### סכום כל המקדמים המולטינומיים מאותה דרגה ''m''
המקרה הפשוט ביותר של המקדם המולטינומי הוא זה של המקדם הבינומי  {n \choose k}, המייצג את מספר האפשרויות לחלק מחרוזת בת *n* אותיות לשתי תת-מחרוזות בנות *k* ו-*n-k* אותיות (ללא חשיבות לסדר האותיות בכל אחת מתת-המחרוזות). סכום כל המקדמים הבינומיים כאשר *k* רץ מ-*1* ל-*n-1* שווה למספר הדרכים לחלק את המחרוזת המקורית לשתי תת-מחרוזות לא ריקות, שניתן לפרשו גם כמספר האפשרויות להרכיב מחרוזת לא ריקה ולא מקסימלית מתוך *n* האותיות כאשר יש חשיבות לסדר תת-המחרוזות (אך אין חשיבות לסדר הפנימי של האותיות בכל תת-מחרוזת). כל אות יכולה להיבחר או לא להיבחר, מה שנותן  2^n חלוקות כאלו, וכאשר לא כוללים את האפשרויות שמתייחסות לקבוצה ריקה ישנן בדיוק  2^n - 2 חלוקות כאלו. את אותו הרעיון ניתן להכליל גם למקרה של מקדמים מולטינומיים מורכבים יותר. למעשה, אם נסמן ב-
 C_{3,n}  את מספר החלוקות האפשרויות של קבוצה בת *n* איברים ל-3 קבוצות לא ריקות (כאשר אין חשיבות לסדר תת-הקבוצות; זהו סכום כל המקדמים המולטינומיים מדרגה 3, חלקי  3! ), נוכל להראות כי מתקיים כלל הנסיגה:

:  C_{3,n+1} = 3C_{3,n} + 2^{n-1} - 1

ההוכחה לכך מורכבת מן הטיעון הבא - לאחר ש"ממצים" את מספר החלוקות המולטינומיות מדרגה 3 של קבוצה התחלתית בת *n* איברים, ניתן לספח איבר נוסף (האיבר ה-*n+1*) בשתי דרכים שונות:

* להוסיף אותו לקבוצה קיימת; עבור כל חלוקה של הקבוצה ההתחלתית, ניתן להוסיף את האיבר לכל אחת מ-3 תת-הקבוצות שלה, מה שנותן  3C_{3,n} אפשרויות.
* להשאיר אותו בנפרד בתור תת-קבוצה בפני עצמה; במקרה זה, יש לחלק את *n* האיברים של הקבוצה ההתחלתית לשתי תת-קבוצות, וכבר נוכחנו לדעת כי ישנן  2^n - 2 חלוקות כאלו. אולם, כל "חצייה" כזאת נספרת למעשה פעמיים, היות שכל אחת משתי תת-הקבוצות של הקבוצה ההתחלתית נספרת בתורה. לפיכך, יש לחלק ב-2 את התוספת, וכך נקבל:

:  C_{3,n+1} = 3C_{3,n} + (2^n - 2)/2 = 3C_{3,n} + 2^{n-1} - 1.

באופן כללי יותר, מספר החלוקות המולטינומיות הלא ריקות מדרגה *m* של קבוצה בת *1+n* איברים מקיים את כלל הנסיגה:

:  C_{m,n+1} = mC_{m,n} + \frac{C_{m-1,n}}{(m-1)!}

כאשר תנאי ההתחלה הם  C_{m,m} = 1 ו- C_{2,n} = 2^{n-1}-1. סכום כל המקדמים המולטינומיים מדרגה *m* של קבוצה בגודל כללי *n* מתקבל אז מהכפלת
 C_{m,n}  ב-  m! . למשל, הערכים הראשונים של  C_{3,n}  (הספירה מתחילה מ-*n=3*) הם:

:  1 , 6, 25, 90,... 

והסכומים המולטינומיים המתאימים הם:

:  6 , 36, 150, 540,... .

באופן כללי,  C_{n,m} שווה למספר סטרלינג מהסוג השני  S(n,m), בעוד שסכום כל המקדמים המולטינומיים המתאים הוא:  m!\cdot S(n,m).

## קישורים חיצוניים
* 
* 

קטגוריה:אלגברה בסיסית
קטגוריה:משפטים בקומבינטוריקה
קטגוריה:משפטים באלגברה
קטגוריה:משפטים בתורת המספרים