מקדם בינומי

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

במחשבון פעולה זו מסומנת בדרך כלל בצורות $n{\rm {C}}r$ או ${\rm {C}}(n,r)$ ). האות $n$ מייצגת את גודל הקבוצה, האות $r$ את גודל התת-קבוצה והאות ${\rm {C}}$ את הקומבינציה.

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

הגדרה מתמטית

לכל $0\leq k\leq n$ המקדם הבינומי של $n$ מעל $k$ הוא ${\binom {n}{k}}={\frac {n!}{k!(n-k)!}}$ כאשר $n!$ הוא ערך העצרת של $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 {n}{k}}={\tbinom {n}{n-k}}$ , כלומר מתקיימת סימטריה בין מקדמי הבינום.

כמו כן,

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

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

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

משולש פסקל

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

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

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

(x+y)^{n}=\sum _{k\,=\,0}^{n}{\binom {n}{k}}x^{k}y^{n-k}

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

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

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

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}}+{\binom {n}{1}}+\cdots +{\binom {n}{n}}=2^{n}

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

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

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

n

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

n

איברים (כאשר הבחירה ללא חזרות) – כל איבר מהמלאי יכול להיבחר או לא להיבחר, מה שנותן

2\cdot 2\cdots 2=2^{n}

אפשרויות. השוויון נובע מכך שמספר האפשרויות להרכיב קבוצה מתוך המלאי הוא למעשה מספר התת-קבוצות של קבוצה בגודל

n

.

3.

\sum _{k\,=\,0}^{n}k{\binom {n}{k}}=n2^{n-1}

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

k{\binom {n}{k}}

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

k

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

n

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

k

(דהיינו

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

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

n

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

n-1

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

n-1

), היינו

n2^{n-1}

.

4.

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

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

2n

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

n

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

n

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

k

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

{n \choose k}

) במספר האפשרויות לבחור קבוצה בגודל n - k מן התת-קבוצה השנייה (

{n \choose n-k}

), כאשר הסכימה עוברת על פני כל הערכים של k מ-0 ל-n. מכאן נקבל:

${2n \choose n}=\sum _{k=0}^{n}{n \choose k}{n \choose n-k}=\sum _{k=0}^{n}{n \choose k}^{2}$ (במעבר האחרון נעזרנו בזהות הראשונה: ${\binom {n}{k}}={\binom {n}{n-k}}$ ).

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

הכללה

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

{\binom {\alpha }{k}}={\frac {\alpha ^{\underline {k}}}{k!}}={\frac {\alpha (\alpha -1)(\alpha -2)\cdots (\alpha -k+1)}{k(k-1)(k-2)\cdots 1}}{\text{ }}\forall k\in \mathbb {N} ,\alpha \in \mathbb {R} .

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

${\begin{aligned}(x+y)^{r}&=\sum _{k=0}^{r}{r \choose 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 .\end{aligned}}$