בקומבינטוריקה, זהות ונדרמונד (או קונבולוציית ונדרמונד) היא הזהות הבאה עבור מקדמים בינומיים: ∑ j = 0 k ( m j ) ( n k − j ) = ( m + n k ) {\displaystyle \sum _{j\,=\,0}^{k}{\binom {m}{j}}{\binom {n}{k-j}}={\binom {m+n}{k}}} הזהות נקראת על שם אלכסנדר ונדרמונד (1772), אף שהייתה ידועה כבר ב-1303 למתמטיקאי הסיני צ'ו שיצ'י (אנ'). לזהות זו הכללות רבות, וביניהן: ∑ k 1 + ⋯ + k p = k ( n 1 k 1 ) ⋯ ( n p k p ) = ( n 1 + ⋯ + n p k ) {\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}}} הוכחה קומבינטורית יהיו n {\displaystyle n} כדורים אדומים ו- m {\displaystyle m} כדורים שחורים. אגף ימין של הזהות מונה כמה דרכים ניתן לבחור k {\displaystyle k} כדורים מתוך n + m {\displaystyle n+m} הכדורים. הביטוי המסוכם באגף שמאל מונה כמה דרכים ניתן לבחור את k {\displaystyle k} הכדורים האלו כאשר j {\displaystyle j} מתוכם שחורים והשאר אדומים; אך הסכום מאפשר ל- j {\displaystyle j} לקבל ערך כלשהו, כך ששני האגפים סופרים את אותה הקבוצה. באמצעות פונקציות יוצרות ∑ k = 0 m + n ( m + n k ) x k = ( 1 + x ) m + n = ( 1 + x ) m ( 1 + x ) n = [ ∑ a = 0 m ( m a ) x a ] [ ∑ b = 0 n ( n b ) x b ] = [ ( m 0 ) + ( m 1 ) x + ⋯ + ( m m − 1 ) x m − 1 + ( m m ) x m ] [ ( n 0 ) + ( n 1 ) x + ⋯ + ( n n − 1 ) x n − 1 + ( n n ) x n ] = ( m 0 ) ( n 0 ) + [ ( m 0 ) ( n 1 ) + ( m 1 ) ( n 0 ) ] x + ⋯ + [ ( m m − 1 ) ( n n ) + ( m m ) ( n n − 1 ) ] x m + n − 1 + ( m m ) ( n n ) x m + n = ∑ k = 0 m + n ( ∑ r = 0 k ( m r ) ( n k − r ) ) x k {\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}}} באינדוקציה ∑ j = 0 k ( m j ) ( n k − j ) = ∑ j = 0 k k − j k ( m j ) ( n k − j ) + ∑ j = 0 k j k ( m j ) ( n k − j ) = ∑ j = 0 k − 1 n − k + j + 1 k ( m j ) ( n k − j − 1 ) + ∑ j = 1 k m − j + 1 k ( m j − 1 ) ( n k − j ) = ∑ j = 0 k − 1 n − k + j + 1 k ( m j ) ( n k − j − 1 ) + ∑ j = 0 k − 1 m − j k ( m j ) ( n k − j − 1 ) = ∑ j = 0 k − 1 m + n − k + 1 k ( m j ) ( n k − j − 1 ) = m + n − k + 1 k ∑ j = 0 k − 1 ( m j ) ( n k − j − 1 ) = m + n − k + 1 k ( n + m k − 1 ) = ( m + n − k + 1 ) ( m + n ) ! k ( k − 1 ) ! ( m + n − k + 1 ) ! = ( m + n ) ! k ! ( m + n − k ) ! = ( m + n k ) {\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 (באנגלית) Loading related searches...Wikiwand - on Seamless Wikipedia browsing. On steroids.
![{\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}}}](//wikimedia.org/api/rest_v1/media/math/render/svg/70ed6590129535fc319f5ce80cb07029593292a1)
![{\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}}}](http://wikimedia.org/api/rest_v1/media/math/render/svg/70ed6590129535fc319f5ce80cb07029593292a1)
