בקומבינטוריקה , זהות ונדרמונד (או קונבולוציית ונדרמונד ) היא הזהות הבאה עבור מקדמים בינומיים :
∑
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}}}
קישורים חיצוניים
עריכה
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/70ed6590129535fc319f5ce80cb07029593292a1)
