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

בקומבינטוריקה, זהות ונדרמונד או קונבולוציית ונדרמונד היא הזהות הבאה עבור מקדמים בינומיים: $\sum _{j=0}^{k}{\binom {m}{j}}{\binom {n}{k-j}}={\binom {m+n}{k}}$

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

לזהות זו יש הכללות רבות, וביניהן: $\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}}$

הוכחה

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

הוכחה באמצעות פונקציות יוצרות: לפי נוסחת הבינום, $(1+x)^{n}=\sum _{j=0}^{n}{\binom {n}{j}}x^{j}$ ו- $(1+x)^{m}=\sum _{i=0}^{m}{\binom {m}{i}}x^{i}$ . המכפלה היא $\ \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}$ , ולכן המקדם של $\ x^{k}$ הוא $\ \sum _{j}{\binom {n}{j}}{\binom {m}{k-j}}$ , שהוא אגף ימין של הזהות. מצד שני, המכפלה שווה ל- $\ (1+x)^{n}(1+x)^{m}=(1+x)^{n+m}$ ולכן המקדם של $\ x^{k}$ הוא $\ {\binom {n+m}{k}}$ , וזהו אגף שמאל.

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

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