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

מתוך המכלול, האנציקלופדיה היהודית
קפיצה לניווט קפיצה לחיפוש

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

j=0k(mj)(nkj)=(m+nk)

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

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

k1++kp=k(n1k1)(npkp)=(n1++npk)

הוכחה

קומבינטורית

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

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

k=0m+n(m+nk)xk=(1+x)m+n=(1+x)m(1+x)n=[a=0m(ma)xa][b=0n(nb)xb]=[(m0)+(m1)x++(mm1)xm1+(mm)xm][(n0)+(n1)x++(nn1)xn1+(nn)xn]=(m0)(n0)+[(m0)(n1)+(m1)(n0)]x++[(mm1)(nn)+(mm)(nn1)]xm+n1+(mm)(nn)xm+n=k=0m+n(r=0k(mr)(nkr))xk

באינדוקציה

j=0k(mj)(nkj)=j=0kkjk(mj)(nkj)+j=0kjk(mj)(nkj)=j=0k1nk+j+1k(mj)(nkj1)+j=1kmj+1k(mj1)(nkj)=j=0k1nk+j+1k(mj)(nkj1)+j=0k1mjk(mj)(nkj1)=j=0k1m+nk+1k(mj)(nkj1)=m+nk+1kj=0k1(mj)(nkj1)=m+nk+1k(n+mk1)=(m+nk+1)(m+n)!k(k1)!(m+nk+1)!=(m+n)!k!(m+nk)!=(m+nk)

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

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

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