מקדם בינומי

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

בקומבינטוריקה, מקדם בינומי ${\tbinom {n}{k}}$ הוא מספר תת־הקבוצות בגודל $k$ שניתן לבחור מתוך קבוצה בגודל $n$. מכיוון שמדובר בתת־קבוצות, הבחירה מתבצעת ללא חזרות וללא חשיבות לסדר. למשל, מספר האפשרויות למלא טופס לוטו, שצריך לבחור 6 מספרים מתוך 37 הוא ${\tbinom {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)\cdots (n-k+1)={\frac {n!}{(n-k)!}}$

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

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

כמו כן,

${\binom {n}{k}}={\frac {n(n-1)\cdots {\bigl (}n-(k-1){\bigr )}}{k(k-1)\cdots 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}}+\cdots +{\binom {n}{n}}=2^{n}$

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

3. $\sum _{k\,=\,0}^{n}k\cdot {\binom {n}{k}}=2^{n-1}n$

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

4. $\sum _{k\,=\,0}^{n}{\binom {n}{k}}^{2}={\binom {2n}{n}}$

הוכחה: נחלק קבוצה בגודל $2n$ לשתי תת־קבוצות בגודל $n$. מספר האפשרויות לבחור ממנה קבוצה בגודל $n$ שווה לסכום של מכפלות מספר האפשרויות לבחור קבוצה בגודל $k$ מתת־הקבוצה הראשונה (${\tbinom {n}{k}}$) במספר האפשרויות לבחור קבוצה בגודל $n-k$ מתת־הקבוצה השנייה (${\tbinom {n}{n-k}}$), כאשר הסכימה עוברת על פני כל הערכים של $k$ מ־0 ל־$n$. מכאן נקבל:

${\binom {2n}{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 {\alpha }{k}}={\frac {\alpha ^{\underline {k}}}{k!}}={\frac {\alpha (\alpha -1)\cdots (\alpha -k+1)}{k(k-1)\cdots 1}}\quad \forall k\in \mathbb {N} ,\alpha \in \mathbb {R}$

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

$(x+y)^{r}=\sum _{k\,=\,0}^{\infty }{\binom {r}{k}}x^{r-k}y^{k}=x^{r}+rx^{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}+\cdots$

ראו גם

• הבינום של ניוטון
• משולש פסקל
• מספר קטלן

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

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