זהות ונדרמונד
בקומבינטוריקה, זהות ונדרמונד או קונבולוציית ונדרמונד היא הזהות הבאה עבור מקדמים בינומיים: $ \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}} $
קישורים חיצוניים
- זהות ונדרמונד, באתר MathWorld (באנגלית)
זהות ונדרמונד34291039Q3147827