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

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

\sum_{j = 0}^{k} (\binom{m}{j}) (\binom{n}{k - j}) = (\binom{m + n}{k})

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

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

\sum_{k_{1} + \dots + k_{p} = k} (\binom{n_{1}}{k_{1}}) \dots (\binom{n_{p}}{k_{p}}) = (\binom{n_{1} + \dots + n_{p}}{k})

הוכחה

קומבינטורית

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

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

\begin{matrix} \sum_{k = 0}^{m + n} (\binom{m + n}{k}) x^{k} & = (1 + x)^{m + n} = (1 + x)^{m} (1 + x)^{n} \\ = [\sum_{a = 0}^{m} (\binom{m}{a}) x^{a}] [\sum_{b = 0}^{n} (\binom{n}{b}) x^{b}] \\ = [(\binom{m}{0}) + (\binom{m}{1}) x + \dots + (\binom{m}{m - 1}) x^{m - 1} + (\binom{m}{m}) x^{m}] [(\binom{n}{0}) + (\binom{n}{1}) x + \dots + (\binom{n}{n - 1}) x^{n - 1} + (\binom{n}{n}) x^{n}] \\ = (\binom{m}{0}) (\binom{n}{0}) + [(\binom{m}{0}) (\binom{n}{1}) + (\binom{m}{1}) (\binom{n}{0})] x + \dots + [(\binom{m}{m - 1}) (\binom{n}{n}) + (\binom{m}{m}) (\binom{n}{n - 1})] x^{m + n - 1} + (\binom{m}{m}) (\binom{n}{n}) x^{m + n} \\ = \sum_{k = 0}^{m + n} (\sum_{r = 0}^{k} (\binom{m}{r}) (\binom{n}{k - r})) x^{k} \end{matrix}

באינדוקציה

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

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

תבנית:MathWorld

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

תוכן עניינים

הוכחה

קומבינטורית

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

באינדוקציה

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

תפריט ניווט

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

הוכחה

קומבינטורית

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

באינדוקציה

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

תפריט ניווט

חיפוש