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

ב[[קומבינטוריקה]], '''זהות ונדרמונד '''(או '''קונבולוציית ונדרמונד''') היא הזהות הבאה עבור [[מקדם בינומי|מקדמים בינומיים]]:

:<math>\sum_{j=0}^k\binom{m}{j}\binom{n}{k-j}=\binom{m+n}{k}</math><math />

לכל [[מספר שלם|מספרים שלמים]] אי-שליליים ''k'', ''m'', ''n''. זהות זו קרויה על שם [[אלכסנדר ונדרמונד|אלכסנדר-תאופיל ונדרמונד]] (1772), למרות שהייתה ידועה כבר ב-1303 על ידי המתמטיקאי הסיני [[צ'ו שיצ'י]] {{אנ|Zhu Shijie}}.

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

== הוכחה ==
'''הוכחה קומבינטורית''': אגף ימין של הזהות סופר כמה דרכים יש לבחור k כדורים מכד שיש בו n כדורים אדומים ו-m כדורים שחורים. הביטוי המסוכם באגף שמאל סופר כמה דרכים יש לבחור את k הכדורים האלו כאשר j מתוכם שחורים והשאר אדומים; אבל הסכום מאפשר ל-j לקבל ערך כלשהו, כך ששני האגפים סופרים את אותה קבוצה.

'''הוכחה באמצעות פונקציות יוצרות''': לפי נוסחת הבינום, <math>(1+x)^n = \sum_{j=0}^{n} \binom{n}{j} x^j</math> ו-<math>(1+x)^m = \sum_{i=0}^{m} \binom{m}{i} x^i</math>. המכפלה היא <math>\ \sum_{j=0}^{n} \sum_{i=0}^{m} \binom{n}{j}\binom{m}{i} x^{i+j} = \sum_{k\geq 0} \left(\sum_{i+j=k}\binom{n}{j}\binom{m}{i}\right)x^{k}</math>, ולכן המקדם של <math>\ x^k</math> הוא <math>\ \sum_{j}\binom{n}{j}\binom{m}{k-j}</math>, שהוא אגף ימין של הזהות. מצד שני, המכפלה שווה ל-<math>\ (1+x)^n(1+x)^m = (1+x)^{n+m}</math> ולכן המקדם של <math>\ x^k</math> הוא <math>\ \binom{n+m}{k}</math>, וזהו אגף שמאל.

'''הוכחה באינדוקציה''' על k:

<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}}

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