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

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

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

עבור מספרים שלמים אי־שליליים $k, m, n$ . הזהות נקראת על שם אלכסנדר-תאופיל ונדרמונד (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})

הוכחה

קומבינטורית

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

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

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

באינדוקציה

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

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

שגיאות פרמטריות בתבנית:מיון ויקיפדיה
שימוש בפרמטרים מיושנים [ דרגה ] זהות ונדרמונד24615899

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

תוכן עניינים

הוכחה

קומבינטורית

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

באינדוקציה

תפריט ניווט

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

הוכחה

קומבינטורית

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

באינדוקציה

תפריט ניווט

חיפוש