מקדם בינומי

בקומבינטוריקה, מקדם בינומי $(\binom{n}{k})$ הוא מספר תת־הקבוצות בגודל $k$ שניתן לבחור מתוך קבוצה בגודל $n$ . מכיוון שמדובר בתת־קבוצות, הבחירה מתבצעת ללא חזרות וללא חשיבות לסדר. למשל, מספר האפשרויות למלא טופס לוטו, שצריך לבחור 6 מספרים מתוך 37 הוא $(\binom{37}{6})$

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

הגדרה מתמטית

לכל $0 \leq k \leq n$ נגדיר:

(\binom{n}{k}) \equiv \frac{n!}{k! (n - k)!}

כאשר $!$ פונקציית העצרת.

ניתן להבין את ההגדרה באופן הבא – אם מקבוצה בגודל $n$ נרצה לבחור תת־קבוצה בגודל $k$ ללא חשיבות לסדר, אז יש $n$ אפשרויות לבחירת האבר הראשון, $n - 1$ אפשרויות לבחירת השני, וכן הלאה עד ל־ $n - k + 1$ אפשרויות לבחירת האחרון. סך הכל נקבל שמספר תת־הקבוצות הוא

n (n - 1) \dots (n - k + 1) = \frac{n!}{(n - k)!}

כל תת־קבוצה מופיעה $k!$ פעמים, כמספר התמורות האפשריות שלה. לכן נחלק ב־ $k!$ ונקבל את ההגדרה המבוקשת.

מההגדרה נובעת הזהות החשובה הבאה: $(\binom{n}{k}) = (\binom{n}{n - k})$ , כלומר מתקיימת סימטריה בין מקדמי הבינום.

כמו כן,

(\binom{n}{k}) = \frac{n (n - 1) \dots (n - (k - 1))}{k (k - 1) \dots 2 \cdot 1}

נוסחה זו מאפשרת חישוב קצר ונוח יותר של המקדם הבינומי עבור ערכים קטנים של $k$ . למשל:

(\binom{n}{1}) = n, (\binom{n}{2}) = \frac{n (n - 1)}{2}

משולש פסקל

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

(\binom{n}{m}) = (\binom{n - 1}{m - 1}) + (\binom{n - 1}{m})

עם תנאי ההתחלה

(\binom{0}{0}) = 1, (\binom{n}{n + 1}) = 0, (\binom{n}{- 1}) = 0

הבינום של ניוטון

הבינום של ניוטון הוא נוסחה לפיתוח סכום של שני אברים:

(x + y)^{n} = \sum_{k = 0}^{n} (\binom{n}{k}) x^{n - k} y^{k}

מקרה פרטי של הנוסחה הוא

2^{n} = (1 + 1)^{n} = \sum_{k = 0}^{n} (\binom{n}{k})

המבטא את מספר תת־הקבוצות בגודל כלשהו מתוך קבוצה בגודל $n$ . באגף שמאל, $2^{n}$ אומר שלכל אבר יש שתי אפשרויות, או להיות בתת־קבוצה או שלא. באגף ימין, $\sum_{k = 0}^{n} (\binom{n}{k})$ אומר שנסכום את מספר תת־הקבוצות עם אפס אברים, אבר אחד, שני אברים, $k$ אברים וכן הלאה.

זהויות עם מקדמים בינומיים

1.

(\binom{n}{k}) = (\binom{n}{n - k})

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

(\binom{n}{k}) = \frac{n!}{k! (n - k)!} = \frac{n!}{(n - k)! k!} = (\binom{n}{n - k})

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

k

אברים מתוך

n

היא כמו בחירת

n - k

האברים שלא נבחרו.

2.

(\binom{n}{0}) + \dots + (\binom{n}{n}) = 2^{n}

הוכחה: ראו בפסקה הקודמת.

3.

\sum_{k = 0}^{n} k \cdot (\binom{n}{k}) = 2^{n - 1} n

הוכחה: על האבר הכללי של הטור

k (\binom{n}{k})

ניתן לומר שהוא מכפלת מספר תת־הקבוצות בגודל

k

בגודל תת־הקבוצה, וניתן לפרש אותו באופן קומבינטורי גם כמכפלת מספר האברים

n

בסך הפעמים שכל אבר נבחר כאשר מציינים את כל תת־הקבוצות בגודל

k

(כלומר

n (\binom{n - 1}{k - 1})

). כיוון שכך, סכום הטור שווה למכפלת מספר האברים

n

במספר הפעמים שכל אבר נבחר כאשר מספחים לו תת־קבוצה מתוך קבוצה בגודל

n - 1

(כלומר יש לכפול בגודל קבוצת החזקה של קבוצה בגודל

n - 1

), כלומר

2^{n - 1} n

.

4.

\sum_{k = 0}^{n} {(\binom{n}{k})}^{2} = (\binom{2 n}{n})

הוכחה: נחלק קבוצה בגודל

2 n

לשתי תת־קבוצות בגודל

n

. מספר האפשרויות לבחור ממנה קבוצה בגודל

n

שווה לסכום של מכפלות מספר האפשרויות לבחור קבוצה בגודל

k

מתת־הקבוצה הראשונה (

(\binom{n}{k})

) במספר האפשרויות לבחור קבוצה בגודל

n - k

מתת־הקבוצה השנייה (

(\binom{n}{n - k})

), כאשר הסכימה עוברת על פני כל הערכים של

k

מ־0 ל־

n

. מכאן נקבל:

(\binom{2 n}{n}) = \sum_{k = 0}^{n} (\binom{n}{k}) (\binom{n}{n - k}) = \sum_{k = 0}^{n} {(\binom{n}{k})}^{2}

זהות זו היא מקרה פרטי של זהות ונדרמונד הכללית יותר:

\sum_{j = 0}^{k} (\binom{m}{j}) (\binom{n - m}{k - j}) = (\binom{n}{k})

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

n

אברים לשתי תת־קבוצות של

m

ו־

n - m

אברים. מספר תת־הקבוצות עם

k

אברים (אגף ימין) שווה לסכום באגף שמאל (

k

ו־

k - j

הם מספר האברים שנבחרים מכל תת־קבוצה, בהתאמה).

הכללה

עבור מספרים ממשיים, המקדם ניתן להגדרה ללא פעולת העצרת על ידי:

(\binom{α}{k}) = \frac{α^{\underline{k}}}{k!} = \frac{α (α - 1) \dots (α - k + 1)}{k (k - 1) \dots 1} \forall k \in ℕ, α \in ℝ

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

(x + y)^{r} = \sum_{k = 0}^{\infty} (\binom{r}{k}) x^{r - k} y^{k} = x^{r} + r x^{r - 1} y + \frac{r (r - 1)}{2!} x^{r - 2} y^{2} + \frac{r (r - 1) (r - 2)}{3!} x^{r - 3} y^{3} + \dots

ראו גם

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

מדיה וקבצים בנושא מקדם בינומי בוויקישיתוף

מקדם בינומי

תוכן עניינים

הגדרה מתמטית

משולש פסקל

הבינום של ניוטון

זהויות עם מקדמים בינומיים

הכללה

ראו גם

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

תפריט ניווט

מקדם בינומי

הגדרה מתמטית

משולש פסקל

הבינום של ניוטון

זהויות עם מקדמים בינומיים

הכללה

ראו גם

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

תפריט ניווט

חיפוש