נוסחת הבינום

נתבונן בחזקות של הביטוי $x+y$ .

\begin{align*} (x+y)^0&=1 \\ (x+y)^1&=x+y \\ (x+y)^2&=(x+y)(x+y)=xx+xy+yx+yy \\ (x+y)^3&=(x+y)(x+y)^2=xxx+xxy+xyx+xyy+yxx+yxy+yyx+yyy \\ & \qquad \qquad \qquad \qquad \quad\ 111\quad\;\; 110 \quad\; 101 \quad\; 100 \quad\; 011 \quad\; 010 \quad\; 001 \quad\; 000 \end{align*}

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

\begin{align*} (x+y)^3=(x+y)(x+y)^2=\;&xxx+xxy+xyx+xyy+yxx+yxy+yyx+yyy \\ & \ 111 \quad\; 110 \quad\; 101 \quad\; 100 \quad\; 011 \quad\; 010 \quad\; 001 \quad\; 000 \\ & \;\; x^3 \;\;\;\;\; 3x^2y \quad \quad \quad \quad \quad 3xy^2 \quad \quad \quad \quad \quad \quad \quad \quad y^3 \end{align*}

נשים לב כי מספר האפשרויות שלנו לבחור $k$ אחדים ו- $n-k$ אפסים הוא $\begin{pmatrix}n\\ k\end{pmatrix}$ . כך נוכל לפתח את נוסחה די מעניינת:
לנוסחה $(x+y)^n$ יש $n+1$ מונומים שונים והם: $(x+y)^n=\square x^n+\square x^{n-1}y+\square x^{n-2}y^2+\dots+\square x^1y^{n-1}+\square y^n$ .
זה שקול לנוסחה $\sum_{i=0}^n c_{i}x^iy^{n-i}$ כאשר $c_{i}$ הוא מספר המופעים של $x^iy^{n-i}$ . הוא שווה למספר הוקטורים הבינארים באורך $n$ עם $i$ אחדים(המסמלים איקסים). לכן, זה בדיוק $\begin{pmatrix}n\\ k\end{pmatrix}$ .

משפט (הבינום)

(x+y)^n=\sum_{k=0}^n \begin{pmatrix} n \\ k \end{pmatrix}x^ky^{n-k}

נשים לב כי ניתן לבצע זאת עבור כל $x,y$ ממשיים.

דוגמה

x^n=(x+0)^n=\sum_{k=0}^n \begin{pmatrix} n \\ k \end{pmatrix}x^n y^{n-k}=x^ny^0=x^n

זאת קיבלנו כי עבור כל חזקה שאינה אפס ל-0 נקבל $x^?y^k=0$ שכן $0^k$ עבור $k>0$ מתקיים $0^k=0$ .

משולש פסקל

\begin{matrix} (x+y)^0 = {\color{red}1} \\ (x+y)^1 = {\color{red}1}y + {\color{red}1}x \\ (x+y)^2 = {\color{red}1}y^2 + {\color{red}2}xy + {\color{red}1}x^2 \\ (x+y)^3 = {\color{red}1}y^3 + {\color{red}3}xy^2 + {\color{red}3}x^2y + {\color{red}1}x^3 \\ (x+y)^4 = {\color{red}1}y^4 + {\color{red}4}xy^3 + {\color{red}6}x^2y^2 + {\color{red}4}x^3y + {\color{red}1}x^4 \\ (x+y)^5 = {\color{red}1}y^5 + {\color{red}5}xy^4 + {\color{red}10}x^2y^3 + {\color{red}10}x^3y^2 + {\color{red}5}x^4y + {\color{red}1}x^5 \\ \\ \begin{gather} (x+y)^n=\sum_{k=0}^n {\color{red} \begin{pmatrix} n \\ k \end{pmatrix}}x^ky^{n-k} \end{gather} \end{matrix}

נשים לב כי יש סימטריות במקדמי הבינום. זה נובע מכך ש- $\begin{pmatrix}n\\ k\end{pmatrix}=\begin{pmatrix}n\\ n-k\end{pmatrix}$ .
נשים לב כי האיבר הראשון בכל שורה הוא $1$ שכן הוא $\begin{pmatrix}k\\ 0\end{pmatrix}$ . לאור הסימטריות נקבל גם כי $\begin{pmatrix}k\\ k\end{pmatrix}=1$ .

משפט

\begin{pmatrix} n\\ k \end{pmatrix}=\begin{pmatrix} n \\ n-k \end{pmatrix}

הוכחה אלגברית:

\begin{pmatrix} n \\ k \end{pmatrix}=\frac{n!}{k!(n-k)!} \qquad \begin{pmatrix} n \\ n-k \end{pmatrix}=\frac{n!}{(n-k)!k!}

הוכחה קומבינטורית:
הבעיה: מספר הוקטורים הבינארים עם $k$ אחדים.
פתרון א': בחירת $k$ המקומות לאחדים ללא חזרות וללא חשיבות לסדר. לכן, יש $\begin{pmatrix}n\\ k\end{pmatrix}$ אפשרויות.
פתרון ב': בחירת $n-k$ המקומות לאפסים ללא חזרות וללא חשיבות לסדר. לכן, יש $\begin{pmatrix}n\\ n-k\end{pmatrix}$ אפשרויות.

לכן, מכיוון שאלו שתי פתרונות לאותה הבעיה הם שווים: $\begin{pmatrix}n\\ k\end{pmatrix}=\begin{pmatrix}n\\ n-k\end{pmatrix}$ .
∎

עוד הוכחה קומבינטורית:
בעיה: מספר תתי הקבוצות $X$ של $\left\{ 1,2,\dots,n \right\}$ בגודל $k$ .
פתרון א': זהו מספר האפשרויות לבחור $k$ איברים ללא חזרות וללא חשיבות לסדר מתוך $n$ . לכן, יש $\begin{pmatrix}n\\ k\end{pmatrix}$ אפשרויות.
פתרון ב': נוכל להסתכל על מספר תתי הקבוצות המשלימות $\left\{ 1,2,\dots,n \right\}\setminus X$ ואז נקבל $\begin{pmatrix}n\\ n-k\end{pmatrix}$ .

לכן, מכיוון שאלו שתי פתרונות לאותה הבעיה הם שווים: $\begin{pmatrix}n\\ k\end{pmatrix}=\begin{pmatrix}n\\ n-k\end{pmatrix}$ .
∎

נסתכל על שני איברים בשורה ה- $n$ ואיבר נוסף המופיע ביניהם בשורה הבאה:

\begin{matrix} \begin{pmatrix} n \\ k \end{pmatrix} && \begin{pmatrix} n \\ k+1 \end{pmatrix} \\ &\begin{pmatrix} n+1 \\ k+1 \end{pmatrix} \end{matrix}

משפט (זהות משולש פסקל)

\begin{pmatrix} n\\ k \end{pmatrix}+\begin{pmatrix} n \\ k+1 \end{pmatrix}=\begin{pmatrix} n+1 \\ k+1 \end{pmatrix}

הוכחה אלגברית:

\tiny\begin{pmatrix} n \\ k \end{pmatrix}+\begin{pmatrix} n \\ k+1 \end{pmatrix}=\frac{n!}{k!(n-k)!}+\frac{n!}{(k+1)!(n-k-1)!}=\frac{n!}{(k+1)!(n-k)!}((k+1)+(n-k))= \frac{(n+1)!}{(k+1)!(n-k)!}=\begin{pmatrix} n+1 \\ k+1 \end{pmatrix}

∎

הערה (כללי אצבע)

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

הוכחה קומבינטורית:
בעיה: מספר המילים הבינאריות באורך $n+1$ עם $k+1$ אחדים.
פתרון א': זוהי בחירה של $k+1$ איברים ללא חזרות וללא חשיבות לסדר מתוך $n+1$ איברים. לכן, $\begin{pmatrix}n+1\\ k+1\end{pmatrix}$ .
פתרון ב': נסתכל על הביט האחרון ונפריד למקרים:

מקרה א' - הביט האחרון הוא $1$ ואז נותר לנו לבחור $k$ אחדים מתוך $n$ שזה בדיוק $\begin{pmatrix}n\\ k\end{pmatrix}$
מקרה ב' - הביט האחרון הוא 0 ואז נותר לנו לבחור $k+1$ אחדים מתוך $n$ שזה בדיוק $\begin{pmatrix}n \\ k+1\end{pmatrix}$ .

לפי עקרון האיחוד מספר האפשרויות בפתרון ב' הוא $\begin{pmatrix}n\\ k\end{pmatrix}+\begin{pmatrix}n\\ k+1\end{pmatrix}$ .
אזי, מכיוון שאלו שתי פתרונות לאותה בעיה קומבינטורית הפתרונות שקולים ולכן $\begin{pmatrix}n+1\\ k+1\end{pmatrix}=\begin{pmatrix}n\\ k\end{pmatrix}+\begin{pmatrix}n\\ k+1\end{pmatrix}$ .
∎

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

\sum_{k=0}^n \begin{pmatrix} n\\ k \end{pmatrix}=(1+1)^n =2^n

נראה כעת הוכחה קומבינטורית לקונספט:
בעיה: מספר המילים הבינאריות באורך $n$ .
פתרון א': יש שתי אפשרויות לכל ביט במילה ולכן מספר האפשרויות הוא(לפי עקרון הכפל) $2^n$ .
פתרון ב': נחלק למקרים לפי מספר האחדים( $k$ ) במילה. נתחום $0\leq k\leq n$ . מספר האפשרויות לבחירת מילה בעלת $k$ אחדים הוא $\begin{pmatrix}n\\ k\end{pmatrix}$ . לפי עקרון הסכום מתקיים: $\displaystyle \sum_{k=0}^n \begin{pmatrix}n\\ k\end{pmatrix}$ .

לכן, מכיוון ששתי הבעיות שקולות פתרונן זהה ולכן:

\sum_{k=0}^n \begin{pmatrix} n \\ k \end{pmatrix}=2^n

∎

נשים לב כי עבור $n>0$ מתקיים:

0=(-1+1)^n =\sum_{k=0}^n \begin{pmatrix} n \\ k \end{pmatrix}(-1)^k =\sum_{\R{\text{ זוגי}}k} \begin{pmatrix} n \\ k \end{pmatrix}-\sum_{\R{\text{ אי-זוגי}}k} \begin{pmatrix} n \\ k \end{pmatrix}

ולכן:

\sum_{\R{\text{ זוגי}}k} \begin{pmatrix} n \\ k \end{pmatrix}=\sum_{\R{\text{ אי-זוגי}}k} \begin{pmatrix} n \\ k \end{pmatrix}

נראה כעת הוכחה קומבינטורית לקונספט:
נגדיר $A$ - קבוצת הוקטורים הבינאריים באורך $n$ עם מספר זוגי של $1$ -ים ו- $B$ - קבוצת הוקטורים הבינאריים באורך $n$ עם מספר אי-זוגי של 1-ים.
נבנה התאמה בין $A$ ל- $B$ בצורה הבאה: לכל מילה ב- $A$ נהפוך את הביט האחרון כדי לקבל איבר מ- $B$ .
הפונקציה הזו היא חח"ע ועל (הוכיחו!)
לכן, לפי משפט, $|A|=|B|$ ולכן:

\sum_{\R{\text{ זוגי}}k} \begin{pmatrix} n \\ k \end{pmatrix}=\sum_{\R{\text{ אי-זוגי}}k} \begin{pmatrix} n \\ k \end{pmatrix}

∎

נוכיח כעת את הביטוי: $\displaystyle \sum_{i=0}^m \begin{pmatrix}k+i\\ k\end{pmatrix}\end{gather}=\begin{pmatrix}k+m+1\\ k+1\end{pmatrix}$ בהוכחה קומבינטורית.
הוכחה:
בעיה: מספר המילים הבינאריות באורך $k+m+1$ עם $k+1$ אחדים.
פתרון א': נוכל לבחור $k+1$ אחדים. זוהי בחירה בלי חזרות ובלי חשיבות לסדר ולכן יש בדיוק $\begin{pmatrix}k+m+1\\ k+1\end{pmatrix}$ אפשרויות.
פתרון ב': נפריד למקרים לפי מיקום ה-1 האחרון במילה (כלומר, ה-1 הימני ביותר). נסמן את מקומו ב- $k+i+1$ . לכן, נדרש לבחור עכשיו מיקומים ל- $k$ אחדים ללא חזרות וללא חשיבות לסדר מתוך $k+i$ מקומות ולכן זה בדיוק $\begin{pmatrix}k+i \\ k\end{pmatrix}$ .
לפי עקרון האיחוד מתקיים כי מספר האפשרויות הוא $\sum_{i=0}^m \begin{pmatrix}k+i\\ k\end{pmatrix}$ .

הבעיות שקולות ולכן הפתרונות זהים ומתקיים: $\begin{gather}\sum_{i=0}^m \begin{pmatrix}k+i\\ k\end{pmatrix}\end{gather}=\begin{pmatrix}k+m+1\\ k+1\end{pmatrix}$
∎

משפט (תכונות משולש פסקל)

א. $\begin{pmatrix}n\\ 0\end{pmatrix}=\begin{pmatrix}n\\ n\end{pmatrix}=1$
ב. $\begin{pmatrix}n\\ k\end{pmatrix}=\begin{pmatrix}n\\ n-k\end{pmatrix}$
ג. $\begin{pmatrix}n\\ k\end{pmatrix}+\begin{pmatrix}n\\ k+1\end{pmatrix}=\begin{pmatrix}n+1 \\ k+1\end{pmatrix}$
ד. $\begin{gather}\sum_{k=0}^n \begin{pmatrix}n\\ k\end{pmatrix}=2^n$
ה. $\displaystyle \sum_{\R{\text{ זוגי}}k}\begin{pmatrix}n \\ k\end{pmatrix}=\sum_{\R{\text{ אי זוגי}}k}\begin{pmatrix}n\\ k\end{pmatrix}=2^{n-1}$ עבור $n>0$ .
ו. $\displaystyle \sum_{i=0}^m \begin{pmatrix}k+i\\ k\end{pmatrix}=\begin{pmatrix}k+m+1\\ k+1\end{pmatrix}$

המולטינום

כעת, נרצה לראות מה יקרה אם יש לנו יותר משני איברים.
נגדיר ל- $k_{1},k_{2},\dots,k_{r}$ שלמים אי-שליליים כך ש- $\sum_{i=1}^r k_{i}=n$ נגדיר:

\begin{pmatrix} n \\ \begin{matrix} k_{1} & k_{2} & \dots & k_{r} \end{matrix} \end{pmatrix}=\frac{n!}{k_{1}!k_{2}!\cdots k_{r}!}

משפט (המולטינום)

(x_{1}+x_{2}+\dots+x_{r})^n=\sum_{k_{1}+k_{2}+\dots+k_{r}=n}\begin{pmatrix} n \\ \begin{matrix} k_{1} & k_{2} & \cdots & k_{r} \end{matrix} \end{pmatrix}x_{1}^{k_{1}}x_{2}^{k_{2}}\cdots x_{r}^{k_{r}}

הסכום על פני כל השלמים האי שליליים כך שסכומם $n$ .

דוגמה

{(x_1 + x_2 + x_3)^2 = \sum_{k_1+k_2+k_3=2} \binom{2}{k_1 \quad k_2 \quad k_3} x_1^{k_1} x_2^{k_2} x_3^{k_3}}

\begin{array}{|ccc|c|c|} \hline \boldsymbol{k_1} & \boldsymbol{k_2} & \boldsymbol{k_3} & \boldsymbol{\binom{2}{k_1 \quad k_2 \quad k_3}} & \boldsymbol{x_1^{k_1} x_2^{k_2} x_3^{k_3}} \\ \hline 0 & 0 & 2 & \frac{2!}{0!\,0!\,2!} = 1 & x_3^2 \\ 0 & 2 & 0 & 1 & x_2^2 \\ 2 & 0 & 0 & 1 & x_1^2 \\ 1 & 1 & 0 & \frac{2!}{1!\,1!\,0!} = 2 & x_1 x_2 \\ 1 & 0 & 1 & 2 & x_1 x_3 \\ 0 & 1 & 1 & 2 & x_2 x_3 \\ \hline \end{array}

(x_1 + x_2 + x_3)^2 = x_1^2 + x_2^2 + x_3^2 + 2x_1x_2 + 2x_1x_3 + 2x_2x_3

זהויות קומבינטוריות

משפט

\sum_{k=1}^n k \begin{pmatrix} n \\ k \end{pmatrix}=n\cdot 2^{n-1}

הוכחה אלגברית:

(x+1)^n =\sum_{k=0}^n \begin{pmatrix} n \\ k \end{pmatrix}x^k

נגזור את שני הביטויים(שכן הם אלמנטרים ולכן גזירים)

n(x+1)^{n-1}=\sum_{k=1}^n \begin{pmatrix} n \\ k \end{pmatrix}kx^{k-1}

נציב $x=1$ ואז:

n\cdot 2^{n-1}=\sum_{k=1}^n \begin{pmatrix} n \\ k \end{pmatrix} k

∎

הוכחה קומבינטורית:
בעיה: מספר המילים הטרנריות(0,1,2) באורך $n$ עם 2 אחד בודד.
פתרון א': נבחר את המקום של ה-2. לכך יש לנו $n$ אפשרויות. לאחר מכן זוהי פשוט מילה בינארית באורך $n-1$ ולכן נוכל למקם את האחדים היכן שנרצה ולכן, לפי עקרון הכפל מתקיים $n\cdot 2^{n-1}$ .
פתרון ב': נבחר את מספר האיברים השונים מ-0 במילה(נסמן $k$ ) - נבחר את מקומותיהם: $\begin{pmatrix}n \\k\end{pmatrix}$ . מתוך ה- $k$ מקומות ללא אפסים יש $k$ אפשרויות לבחור את ה- $2$ .
∎

נוסחת הבינום

נתבונן בחזקות של הביטוי $x+y$ .

\begin{align*} (x+y)^0&=1 \\ (x+y)^1&=x+y \\ (x+y)^2&=(x+y)(x+y)=xx+xy+yx+yy \\ (x+y)^3&=(x+y)(x+y)^2=xxx+xxy+xyx+xyy+yxx+yxy+yyx+yyy \\ & \qquad \qquad \qquad \qquad \quad\ 111\quad\;\; 110 \quad\; 101 \quad\; 100 \quad\; 011 \quad\; 010 \quad\; 001 \quad\; 000 \end{align*}

\begin{align*} (x+y)^3=(x+y)(x+y)^2=\;&xxx+xxy+xyx+xyy+yxx+yxy+yyx+yyy \\ & \ 111 \quad\; 110 \quad\; 101 \quad\; 100 \quad\; 011 \quad\; 010 \quad\; 001 \quad\; 000 \\ & \;\; x^3 \;\;\;\;\; 3x^2y \quad \quad \quad \quad \quad 3xy^2 \quad \quad \quad \quad \quad \quad \quad \quad y^3 \end{align*}

משפט (הבינום)

(x+y)^n=\sum_{k=0}^n \begin{pmatrix} n \\ k \end{pmatrix}x^ky^{n-k}

נשים לב כי ניתן לבצע זאת עבור כל $x,y$ ממשיים.

דוגמה

x^n=(x+0)^n=\sum_{k=0}^n \begin{pmatrix} n \\ k \end{pmatrix}x^n y^{n-k}=x^ny^0=x^n

זאת קיבלנו כי עבור כל חזקה שאינה אפס ל-0 נקבל $x^?y^k=0$ שכן $0^k$ עבור $k>0$ מתקיים $0^k=0$ .

משולש פסקל

\begin{matrix} (x+y)^0 = {\color{red}1} \\ (x+y)^1 = {\color{red}1}y + {\color{red}1}x \\ (x+y)^2 = {\color{red}1}y^2 + {\color{red}2}xy + {\color{red}1}x^2 \\ (x+y)^3 = {\color{red}1}y^3 + {\color{red}3}xy^2 + {\color{red}3}x^2y + {\color{red}1}x^3 \\ (x+y)^4 = {\color{red}1}y^4 + {\color{red}4}xy^3 + {\color{red}6}x^2y^2 + {\color{red}4}x^3y + {\color{red}1}x^4 \\ (x+y)^5 = {\color{red}1}y^5 + {\color{red}5}xy^4 + {\color{red}10}x^2y^3 + {\color{red}10}x^3y^2 + {\color{red}5}x^4y + {\color{red}1}x^5 \\ \\ \begin{gather} (x+y)^n=\sum_{k=0}^n {\color{red} \begin{pmatrix} n \\ k \end{pmatrix}}x^ky^{n-k} \end{gather} \end{matrix}

משפט

\begin{pmatrix} n\\ k \end{pmatrix}=\begin{pmatrix} n \\ n-k \end{pmatrix}

הוכחה אלגברית:

\begin{pmatrix} n \\ k \end{pmatrix}=\frac{n!}{k!(n-k)!} \qquad \begin{pmatrix} n \\ n-k \end{pmatrix}=\frac{n!}{(n-k)!k!}

לכן, מכיוון שאלו שתי פתרונות לאותה הבעיה הם שווים: $\begin{pmatrix}n\\ k\end{pmatrix}=\begin{pmatrix}n\\ n-k\end{pmatrix}$ .
∎

נסתכל על שני איברים בשורה ה- $n$ ואיבר נוסף המופיע ביניהם בשורה הבאה:

\begin{matrix} \begin{pmatrix} n \\ k \end{pmatrix} && \begin{pmatrix} n \\ k+1 \end{pmatrix} \\ &\begin{pmatrix} n+1 \\ k+1 \end{pmatrix} \end{matrix}

משפט (זהות משולש פסקל)

\begin{pmatrix} n\\ k \end{pmatrix}+\begin{pmatrix} n \\ k+1 \end{pmatrix}=\begin{pmatrix} n+1 \\ k+1 \end{pmatrix}

הוכחה אלגברית:

\tiny\begin{pmatrix} n \\ k \end{pmatrix}+\begin{pmatrix} n \\ k+1 \end{pmatrix}=\frac{n!}{k!(n-k)!}+\frac{n!}{(k+1)!(n-k-1)!}=\frac{n!}{(k+1)!(n-k)!}((k+1)+(n-k))= \frac{(n+1)!}{(k+1)!(n-k)!}=\begin{pmatrix} n+1 \\ k+1 \end{pmatrix}

∎

הערה (כללי אצבע)

מקרה א' - הביט האחרון הוא $1$ ואז נותר לנו לבחור $k$ אחדים מתוך $n$ שזה בדיוק $\begin{pmatrix}n\\ k\end{pmatrix}$
מקרה ב' - הביט האחרון הוא 0 ואז נותר לנו לבחור $k+1$ אחדים מתוך $n$ שזה בדיוק $\begin{pmatrix}n \\ k+1\end{pmatrix}$ .

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

\sum_{k=0}^n \begin{pmatrix} n\\ k \end{pmatrix}=(1+1)^n =2^n

לכן, מכיוון ששתי הבעיות שקולות פתרונן זהה ולכן:

\sum_{k=0}^n \begin{pmatrix} n \\ k \end{pmatrix}=2^n

∎

נשים לב כי עבור $n>0$ מתקיים:

0=(-1+1)^n =\sum_{k=0}^n \begin{pmatrix} n \\ k \end{pmatrix}(-1)^k =\sum_{\R{\text{ זוגי}}k} \begin{pmatrix} n \\ k \end{pmatrix}-\sum_{\R{\text{ אי-זוגי}}k} \begin{pmatrix} n \\ k \end{pmatrix}

ולכן:

\sum_{\R{\text{ זוגי}}k} \begin{pmatrix} n \\ k \end{pmatrix}=\sum_{\R{\text{ אי-זוגי}}k} \begin{pmatrix} n \\ k \end{pmatrix}

\sum_{\R{\text{ זוגי}}k} \begin{pmatrix} n \\ k \end{pmatrix}=\sum_{\R{\text{ אי-זוגי}}k} \begin{pmatrix} n \\ k \end{pmatrix}

∎

הבעיות שקולות ולכן הפתרונות זהים ומתקיים: $\begin{gather}\sum_{i=0}^m \begin{pmatrix}k+i\\ k\end{pmatrix}\end{gather}=\begin{pmatrix}k+m+1\\ k+1\end{pmatrix}$
∎

משפט (תכונות משולש פסקל)

המולטינום

\begin{pmatrix} n \\ \begin{matrix} k_{1} & k_{2} & \dots & k_{r} \end{matrix} \end{pmatrix}=\frac{n!}{k_{1}!k_{2}!\cdots k_{r}!}

משפט (המולטינום)

(x_{1}+x_{2}+\dots+x_{r})^n=\sum_{k_{1}+k_{2}+\dots+k_{r}=n}\begin{pmatrix} n \\ \begin{matrix} k_{1} & k_{2} & \cdots & k_{r} \end{matrix} \end{pmatrix}x_{1}^{k_{1}}x_{2}^{k_{2}}\cdots x_{r}^{k_{r}}

הסכום על פני כל השלמים האי שליליים כך שסכומם $n$ .

דוגמה

{(x_1 + x_2 + x_3)^2 = \sum_{k_1+k_2+k_3=2} \binom{2}{k_1 \quad k_2 \quad k_3} x_1^{k_1} x_2^{k_2} x_3^{k_3}}

\begin{array}{|ccc|c|c|} \hline \boldsymbol{k_1} & \boldsymbol{k_2} & \boldsymbol{k_3} & \boldsymbol{\binom{2}{k_1 \quad k_2 \quad k_3}} & \boldsymbol{x_1^{k_1} x_2^{k_2} x_3^{k_3}} \\ \hline 0 & 0 & 2 & \frac{2!}{0!\,0!\,2!} = 1 & x_3^2 \\ 0 & 2 & 0 & 1 & x_2^2 \\ 2 & 0 & 0 & 1 & x_1^2 \\ 1 & 1 & 0 & \frac{2!}{1!\,1!\,0!} = 2 & x_1 x_2 \\ 1 & 0 & 1 & 2 & x_1 x_3 \\ 0 & 1 & 1 & 2 & x_2 x_3 \\ \hline \end{array}

(x_1 + x_2 + x_3)^2 = x_1^2 + x_2^2 + x_3^2 + 2x_1x_2 + 2x_1x_3 + 2x_2x_3

זהויות קומבינטוריות

משפט

\sum_{k=1}^n k \begin{pmatrix} n \\ k \end{pmatrix}=n\cdot 2^{n-1}

הוכחה אלגברית:

(x+1)^n =\sum_{k=0}^n \begin{pmatrix} n \\ k \end{pmatrix}x^k

נגזור את שני הביטויים(שכן הם אלמנטרים ולכן גזירים)

n(x+1)^{n-1}=\sum_{k=1}^n \begin{pmatrix} n \\ k \end{pmatrix}kx^{k-1}

נציב $x=1$ ואז:

n\cdot 2^{n-1}=\sum_{k=1}^n \begin{pmatrix} n \\ k \end{pmatrix} k

∎

3 - הבינום של ניוטון ומשולש פסקל

קומבינטוריקה למדעי המחשב

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

3 - הבינום של ניוטון ומשולש פסקל

קומבינטוריקה למדעי המחשב

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

נוסחת הבינום

משולש פסקל

המולטינום

זהויות קומבינטוריות

נוסחת הבינום

משולש פסקל

המולטינום

זהויות קומבינטוריות