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

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

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

עבור m מספר טבעי ו-n מספר אי-שלילי (חיובי או אפס), מתקיים:
:<math>(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}\,,</math>
כאשר
:<math> {n \choose k_1, k_2, \ldots, k_m}
 = \frac{n!}{k_1!\, k_2! \cdots k_m!}</math>
הוא המקדם המולטינומי, המהווה הכללה של המקדם הבינומי.

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

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

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

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

:<math>(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.</math>

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

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

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

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

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

: <math> C_{3,n+1} = 3C_{3,n} + 2^{n-1} - 1</math>

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

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

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

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

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

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

: <math> 1 , 6, 25, 90,... </math>

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

: <math> 6 , 36, 150, 540,... </math>.

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

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

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