זהות ונדרמונד

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

${\displaystyle \sum _{j\,=\,0}^{k}{\binom {m}{j}}{\binom {n}{k-j}}={\binom {m+n}{k}}}$

הזהות נקראת על שם אלכסנדר ונדרמונד (1772), אף שהייתה ידועה כבר ב-1303 למתמטיקאי הסיני צ'ו שיצ'י (אנ').

לזהות זו הכללות רבות, וביניהן:

${\displaystyle \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}}}$

הוכחה

קומבינטורית

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

באמצעות פונקציות יוצרות

$${\displaystyle {\begin{aligned}\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{aligned}}}$$

באינדוקציה

${\displaystyle {\begin{alignedat}{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{alignedat}}}$

קישורים חיצוניים

• זהות ונדרמונד, באתר MathWorld (באנגלית)