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

מתוך המכלול, האנציקלופדיה היהודית
קפיצה לניווט קפיצה לחיפוש

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

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

עבור m מספר חיובי ו-n מספר אי-שלילי (חיובי או אפס), מתקיים:

הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (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}\,,}

כאשר

הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {n \choose k_1, k_2, \ldots, k_m} = \frac{n!}{k_1!\, k_2! \cdots k_m!}}

הוא המקדם המולטינומי, המהווה הכללה של המקדם הבינומי.

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

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

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

דוגמה

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

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

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

כאמור, המקדם הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {n \choose k_1, k_2, \ldots, k_m}= \frac{n!}{k_1!\, k_2! \cdots k_m!}} נקרא המקדם המוליטנומי. למקדם זה יש משמעות קומבינטורית, המכלילה את משמעות המקדם הבינומי: הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {n \choose k_1, k_2, \ldots, k_m}} היא מספר הדרכים לחלק n עצמים שונים ל-m קבוצות, כך שבקבוצה הראשונה יש k1 עצמים, בקבוצה השנייה k2 עצמים וכן הלאה.

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

דוגמה

נחשב את מספר המחרוזות השונות שאפשר להרכיב בעזרת האותיות b,a,n,a,n,a - סה"כ יש כאן 6 אותיות, מתוכן פעם אחת b, פעמיים n, ושלוש פעמים a - ולכן התשובה היא .

זהויות מולטינומיות

סכום כל המקדמים המולטינומיים מאותה דרגה m

המקרה הפשוט ביותר של המקדם המולטינומי הוא זה של המקדם הבינומי הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {n \choose k}} , המייצג את מספר האפשרויות לחלק מחרוזת בת n אותיות לשתי תת-מחרוזות בנות k ו-n-k אותיות (ללא חשיבות לסדר האותיות בכל אחת מתת-המחרוזות). סכום כל המקדמים הבינומיים כאשר k רץ מ-1 ל-n-1 שווה למספר הדרכים לחלק את המחרוזת המקורית לשתי תת-מחרוזות לא ריקות, שניתן לפרשו גם כמספר האפשרויות להרכיב מחרוזת לא ריקה ולא מקסימלית מתוך n האותיות כאשר יש חשיבות לסדר תת-המחרוזות (אך אין חשיבות לסדר הפנימי של האותיות בכל תת-מחרוזת). כל אות יכולה להיבחר או לא להיבחר, מה שנותן הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 2^n} חלוקות כאלו, וכאשר לא כוללים את האפשרויות שמתייחסות לקבוצה ריקה ישנן בדיוק הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 2^n - 2} חלוקות כאלו. את אותו הרעיון ניתן להכליל גם למקרה של מקדמים מולטינומיים מורכבים יותר. למעשה, אם נסמן ב- הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle C_{3,n} } את מספר החלוקות האפשרויות של קבוצה בת n איברים ל-3 קבוצות לא ריקות (כאשר אין חשיבות לסדר תת-הקבוצות; זהו סכום כל המקדמים המולטינומיים מדרגה 3, חלקי הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 3! } ), נוכל להראות כי מתקיים כלל הנסיגה:

הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle C_{3,n+1} = 3C_{3,n} + 2^{n-1} - 1}

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

  • להוסיף אותו לקבוצה קיימת; עבור כל חלוקה של הקבוצה ההתחלתית, ניתן להוסיף את האיבר לכל אחת מ-3 תת-הקבוצות שלה, מה שנותן הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 3C_{3,n}} אפשרויות.
  • להשאיר אותו בנפרד בתור תת-קבוצה בפני עצמה; במקרה זה, יש לחלק את n האיברים של הקבוצה ההתחלתית לשתי תת-קבוצות, וכבר נוכחנו לדעת כי ישנן הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 2^n - 2} חלוקות כאלו. אולם, כל "חצייה" כזאת נספרת למעשה פעמיים, היות שכל אחת משתי תת-הקבוצות של הקבוצה ההתחלתית נספרת בתורה. לפיכך, יש לחלק ב-2 את התוספת, וכך נקבל:
הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle C_{3,n+1} = 3C_{3,n} + (2^n - 2)/2 = 3C_{3,n} + 2^{n-1} - 1} .

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

הפענוח נכשל (שגיאת המרה. השרת ("https://en.wikipedia.org/api/rest_") השיב: "Cannot get mml. Server problem."): {\displaystyle C_{m,n+1}=mC_{m,n}+{\frac {C_{m-1,n}}{(m-1)!}}}

כאשר תנאי ההתחלה הם הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle C_{m,m} = 1} ו-הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle C_{2,n} = 2^{n-1}-1} . סכום כל המקדמים המולטינומיים מדרגה m של קבוצה בגודל כללי n מתקבל אז מהכפלת הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle C_{m,n} } ב- הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle m! } . למשל, הערכים הראשונים של הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle C_{3,n} } (הספירה מתחילה מ-n=3) הם:

הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 1 , 6, 25, 90,... }

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

.

באופן כללי, הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle C_{n,m}} שווה למספר סטירלינג מהסוג השני הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle S(n,m)} , בעוד שסכום כל המקדמים המולטינומיים המתאים הוא: הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle m!\cdot S(n,m)} .

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

סמל המכלול גמרא 2.PNG
הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0