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

בקומבינטוריקה, זהות ונדרמונד או קונבולוציית ונדרמונד היא הזהות הבאה עבור מקדמים בינומיים: $\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} (\sum_{i + j = k} (\binom{n}{j}) (\binom{m}{i})) 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{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}$

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

זהות ונדרמונד, באתר MathWorld (באנגלית)

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

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

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

הוכחה

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

תפריט ניווט

חיפוש