מקדם בינומי

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

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

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

הגדרה מתמטית

לכל $0\leq k\leq 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 {n}{k}}={\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}}$

משולש פסקל

ערך מורחב – משולש פסקל

משולש פסקל מספק נוסחת נסיגה אשר מאפשרת לחשב את מקדמי הבינום ומתבטאת בזהות הבאה:
${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$

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

ערך מורחב – הבינום של ניוטון

הבינום של ניוטון הוא נוסחא לפיתוח סכום של שני איברים. הנוסחא בצורתה הבסיסית היא: $(x+y)^{n}=\sum _{k=0}^{n}{n \choose k}x^{k}y^{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}$

ראו גם

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