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

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

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

עבור 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₁ עדk_m כך שסכום כל k_i הוא n. כלומר, עבור כל איבר בסכום, סכום המעריכים בחזקות חייב להסתכם ל-n. (נציין כי איברים מהצורה x⁰ נלקחים בתור 1, אף אם x הוא 0).

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

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

דוגמה

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

(a+b+c)^{3}=a^{3}+b^{3}+c^{3}+3a^{2}b+3a^{2}c+3b^{2}a+3b^{2}c+3c^{2}a+3c^{2}b+6abc.

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

המקדם המולטינומי בקומבינטוריקה

כאמור, המקדם ${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₁ עצמים, בקבוצה השנייה k₂ עצמים וכן הלאה.

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

דוגמה

נחשב את מספר המחרוזות השונות שאפשר להרכיב בעזרת האותיות 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) הם: