מקדם בינומי

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

בקומבינטוריקה, מקדם בינומי  \tbinom nk הוא מספר תת-הקבוצות בגודל k שניתן לבחור מתוך קבוצה בגודל n. מכיוון שמדובר בתת-קבוצות, הבחירה מתבצעת ללא חזרות וללא חשיבות לסדר. לדוגמה, אם שלושה שחקנים מקבוצת כדורגל יצאו עם כרטיס אדום, אז  \tbinom {11}{3} הוא מספר האפשרויות לבחור את אותם שלושה שחקנים (ללא חשיבות לסדר בו הם יצאו מהמשחק).

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

הגדרה מתמטית[עריכת קוד מקור | עריכה]

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

 {n \choose k} = \frac{n!}{k!\,(n-k)!}

כאשר \ n! הוא ערך העצרת של n.

ניתן להבין את ההגדרה באופן הבא - אם נרצה לבחור תת-קבוצה בגודל k עם חשיבות לסדר, אז יש לנו n אפשרויות לבחור את האיבר הראשון בתת-הקבוצה, n-1 אפשרויות לבחור את השני, וכן הלאה עד ל-n-k+1 אפשרויות לבחור את האחרון. סך הכל נקבל שמספר תת-הקבוצות הוא  n(n-1)(n-2)\cdots(n-k+1) = \frac{n!}{(n-k)!}. כל תת-קבוצה מופיעה \ k! פעמים, כמספר התמורות האפשריות שלה. לכן נחלק ב- \ k! ונקבל את ההגדרה המבוקשת.

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

כמו כן,

{ n \choose k} = \frac{n(n-1)\cdot...\cdot (n-(k-1))}{ k(k-1)(k-2) \cdot ... \cdot 1}

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

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

משולש פסקל[עריכת קוד מקור | עריכה]

Postscript-viewer-shaded.png ערך מורחב – משולש פסקל

משולש פסקל מספק נוסחת נסיגה אשר מאפשרת לחשב את מקדמי הבינום ומתבטאת בזהות הבאה:
{n \choose m}={n-1 \choose m-1}+{n-1 \choose m} עם תנאי ההתחלה  {0 \choose 0}=1 ו-  {n \choose n+1}=0 ,  {n \choose -1}=0

הבינום של ניוטון[עריכת קוד מקור | עריכה]

Postscript-viewer-shaded.png ערך מורחב – הבינום של ניוטון

הבינום של ניוטון הוא נוסחה לפיתוח סכום של שני איברים. הנוסחה בצורתה הבסיסית היא: (x+y)^n=\sum_{k=0}^n{n \choose k}x^ky^{n-k}
מקרה פרטי של הנוסחה הוא: 2^n=(1+1)^n=\sum_{k=0}^n{n \choose k}
אשר מבטאת את מספר התת-קבוצות בגודל כלשהו מתוך קבוצה בגודל n. באגף שמאל, \ 2^n אומר שלכל איבר יש שתי אפשרויות, או להיות בתת-קבוצה או שלא. באגף ימין, \sum_{k=0}^n{n \choose k} אומר שנסכום את מספר התת-קבוצות עם אפס איברים, איבר אחד, שני איברים, k איברים וכן הלאה.

זהויות עם מקדמים בינומיים[עריכת קוד מקור | עריכה]

1. \binom{n}{k}=\binom{n}{n-k}
הוכחה: אם ניעזר בנוסחה המפורשת, נקבל \binom{n}{k}=\frac{n!}{k!\left ( n-k \right )!}=\frac{n!}{\left ( n-k \right )!k!}=\binom{n}{n-k}. אם נסתכל על הזהות באופן קומבינטורי, בחירת k איברים מתוך n היא כמו בחירת n-k האיברים שלא נבחרו.
2. \binom{n}{0}+\binom{n}{1}+...+\binom{n}{n}=2^n
הוכחה: אם ניעזר בבינום של ניוטון, נגלה שמתקיים \binom{n}{0}+\binom{n}{1}+...+\binom{n}{n}=\left (1+1  \right )^n=2^n

ראו גם[עריכת קוד מקור | עריכה]