הצגת המקור של הדף "זהות ונדרמונד"

ב[[קומבינטוריקה]], '''זהות ונדרמונד '''(או '''קונבולוציית ונדרמונד''') היא הזהות הבאה עבור [[מקדם בינומי|מקדמים בינומיים]]:
:<math>\sum_{j\,=\,0}^k\binom{m}{j}\binom{n}{k-j}=\binom{m+n}{k}</math>
הזהות נקראת על שם [[אלכסנדר ונדרמונד]] (1772), אף שהייתה ידועה כבר ב-1303 ל[[מתמטיקאי]] הסיני [[צ'ו שיצ'י]] {{אנ|Zhu Shijie}}.

לזהות זו הכללות רבות, וביניהן:
:<math>\sum_{k_1\,+\,\cdots\,+\,k_p\,=\,k}\binom{n_1}{k_1}\cdots\binom{n_p}{k_p}=\binom{n_1+\cdots+n_p}{k}</math>

==הוכחה==
===קומבינטורית===
יהיו <math>n</math> כדורים אדומים ו-<math>m</math> כדורים שחורים.{{ש}}
אגף ימין של הזהות מונה כמה דרכים ניתן לבחור <math>k</math> כדורים מתוך <math>n+m</math> הכדורים.{{ש}}
הביטוי המסוכם באגף שמאל מונה כמה דרכים ניתן לבחור את <math>k</math> הכדורים האלו כאשר <math>j</math> מתוכם שחורים והשאר אדומים; אך הסכום מאפשר ל-<math>j</math> לקבל ערך כלשהו, כך ששני האגפים סופרים את אותה הקבוצה.

===באמצעות פונקציות יוצרות===
:<math display=block>\begin{align}\sum_{k\,=\,0}^{m\,+\,n}{\color{red}\binom{m+n}{k}}x^k&=(1+x)^{m+n}=(1+x)^m(1+x)^n\\&=\left[\sum_{a\,=\,0}^m\binom{m}{a}x^a\right]\left[\sum_{b\,=\,0}^n\binom{n}{b}x^b\right]\\&=\left[\binom{m}{0}+\binom{m}{1}x+\cdots+\binom{m}{m-1}x^{m-1}+\binom{m}{m}x^m\right]\left[\binom{n}{0}+\binom{n}{1}x+\cdots+\binom{n}{n-1}x^{n-1}+\binom{n}{n}x^n\right]\\&=\binom{m}{0}\binom{n}{0}+\left[\binom{m}{0}\binom{n}{1}+\binom{m}{1}\binom{n}{0}\right]x+\cdots+\left[\binom{m}{m-1}\binom{n}{n}+\binom{m}{m}\binom{n}{n-1}\right]x^{m+n-1}+\binom{m}{m}\binom{n}{n}x^{m+n}\\&=\sum_{k\,=\,0}^{m\,+\,n}\left(\,{\color{red}\sum_{r\,=\,0}^k\binom{m}{r}\binom{n}{k-r}}\right)x^k\end{align}</math>

===באינדוקציה===
<math>\begin{alignat}{1}\sum_{j\,=\,0}^k\binom{m}{j}\binom{n}{k-j}
& =\sum_{j\,=\,0}^k\frac{k-j}{k}\binom{m}{j}\binom{n}{k-j}+\sum_{j\,=\,0}^k\frac{j}{k}\binom{m}{j}\binom{n}{k-j}\\
&=\sum_{j\,=\,0}^{k-1}\frac{n-k+j+1}{k}\binom{m}{j}\binom{n}{k-j-1}+\sum_{j\,=\,1}^k\frac{m-j+1}{k}\binom{m}{j-1}\binom{n}{k-j}\\
&=\sum_{j\,=\,0}^{k-1}\frac{n-k+j+1}{k}\binom{m}{j}\binom{n}{k-j-1}+\sum_{j\,=\,0}^{k-1}\frac{m-j}{k}\binom{m}{j}\binom{n}{k-j-1}\\
&=\sum_{j\,=\,0}^{k-1}\frac{m+n-k+1}{k}\binom{m}{j}\binom{n}{k-j-1}\\
&=\frac{m+n-k+1}{k}\sum_{j\,=\,0}^{k-1}\binom{m}{j}\binom{n}{k-j-1}\\
&=\frac{m+n-k+1}{k}\binom{n+m}{k-1}\\
&= \frac{(m+n-k+1)(m+n)!}{k(k-1)!(m+n-k+1)!}\\
&=\frac{(m+n)!}{k!(m+n-k)!}
=\binom{m+n}{k}
\end{alignat}</math>

==קישורים חיצוניים==
* {{MathWorld}}

[[קטגוריה:קומבינטוריקה]]
[[קטגוריה:משפטים בקומבינטוריקה]]
[[קטגוריה:זהויות במתמטיקה|ונדרמונד]]
[[קטגוריה:הוכחות]]