זהות קומבינטורית בשימוש בזהויות הבינום של ניטון

מתמטיקה
1

הוכיחו את הזהות הבאה:

\sum_{k=2,...,n}^{}\binom{k}{2}\binom{n}{k}=\binom{n}{2}\cdot 2^{n-2}

אלגברית: תוך פיתוח הביטוי המופיע באגף שמאל.
וגם קומבינטורית: תוך הצגת בעיה ופתרונה בשתי דרכים שונות.

ניסיתי להיעזר בזהות פסקל ובזהות של \binom{n}{k}=\binom{n}{n-k}, אך ללא הצלחה. אשמח אם תוכלו לפרט בפתרון באיזה זהות השתמשתם בכל פעם.

3

נוכיח את נכונות הזהות בעזרת הוכחה קומבינטורית.
הבעיה הקומבינטורית אותה נגדיר: מהו מספר הדרכים לבנות צוות מ-n אנשים (בכל גודל, לפחות 2) כך שלצוות יהיו בדיוק 2 מנהלים.
צד שמאל: נגדיר את k\in\{2,\ldots,n\} להיות גודל הצוות. לכן נבחר k אנשים מתוך n שיהיו חלק מהצוות ב-{n\choose k} אפשרויות. מתוך k חברי הצוות, נבחר שני מנהלים ב-{k\choose 2}. נסכום את כל האפשרויות ונקבל:

\sum_{k=2}^{n}{k\choose 2}{n\choose k}

צד ימין: נבחר תחילה את שני המנהלים, ולאחר מכן נשלים את שאר חברי הקבוצה מ-n-2 האנשים הנותרים. נבחר את שני המנהלים מתוך n האנשים ב-{n\choose 2} אפשרויות. כמו כן, לכל אדם מתוך n-2 האנשים הנותרים יש שתי אופציות (להיות חלק מהצוות או לא) ולכן מספר האפשרויות הינו 2^{n-2}. בסה"כ ע"פ עקרון הכפל נקבל:

{n\choose 2} \cdot 2^{n-2}

שני הכיוונים פותרים את אותה הבעיה ולכן נכונות הזהות מתקיימת.

2

נוכיח את נכונות הזהות בעזרת הוכחה אלגברית. דרך אחת היא להשתמש בזהות הבאה:

\binom{n}{k}\binom{k}{2}=\binom{n}{2}\binom{n-2}{k-2}

אותה ניתן להוכיח בעזרת פיתוח הביטוי. בעזרת זהות זו נקבל:

\displaystyle\sum_{k=2}^n\binom{n}{k}\binom{k}{2}=\displaystyle\sum_{k=2}^n\binom{n}{2}\binom{n-2}{k-2}=\binom{n}{2}\displaystyle\sum_{k=0}^{n-2}\binom{n-2}{k}=\binom{n}{2}2^{n-2}