עזרה בהוכחת זהות קומבינטורית
צריך להוכיח שאם zz 0<=m<=n zz אזי:
zz sigma (n choose k) (k choose m) = (n choose m) 2^(n-m) zz כאשר ב-sigma באגף שמאל, k רץ מ-0 עד n.
אין לי מושג איך להוכיח את זה אלגברית. אם מישהו יודע איך, אשמח להסבר.
אני מנסה להוכיח קומבינטורית כך:
נראה ששניי צידי הזהות סופים את מספר הדרכים לבחור m סטודנטים מתוך n, לשמש כחברים במועצת התלמידים, כאשר כל שאר n-m הסטודנטים הנותרים, נבחרים לוועד הכיתתי, או שלא נבחרים לוועד הכיתתי.
כלומר הצגתי עכשיו בעיה מילולית, ואני רוצה להראות שאפשר לפתור אותה בשתיי דרכים: דרך אחת היא אגף ימין של הזהות, ודרך שנייה היא אגף שמאל של הזהות.
ובכן, דרך אחת לפתור את הבעיה, היא לבחור תחילה m סטודנטים מתוך כלל n הסטודנטים לשמש כחברים במועצת התלמידים.
כע,עבור כל אחד מ- n-m הסטודנטים שלא נבחרו למועצת התלמידים, יש 2 אפשרויות: להיבחר לוועד הכיתתי, או לא להיבחר לוועד הכיתתי - כלומר zz 2^(n-m) zz אפשרויות.
לפי עקרון המכפלה, מספר האפשרויות הכולל הוא : zz (n choose m) 2^(n-m) zz .
נותר לי להראות שאגף ימין גם מהווה פתרון לבעיה שהצגתי, אבל אני קצת מתקשה עם זה...גם לא ממש ברור לי איך אני מתייחס לסיגמה..
מישהו יודע ויכול לעזור??
תודה.
צריך להוכיח שאם zz 0<=m<=n zz אזי:
zz sigma (n choose k) (k choose m) = (n choose m) 2^(n-m) zz כאשר ב-sigma באגף שמאל, k רץ מ-0 עד n.
אין לי מושג איך להוכיח את זה אלגברית. אם מישהו יודע איך, אשמח להסבר.
אני מנסה להוכיח קומבינטורית כך:
נראה ששניי צידי הזהות סופים את מספר הדרכים לבחור m סטודנטים מתוך n, לשמש כחברים במועצת התלמידים, כאשר כל שאר n-m הסטודנטים הנותרים, נבחרים לוועד הכיתתי, או שלא נבחרים לוועד הכיתתי.
כלומר הצגתי עכשיו בעיה מילולית, ואני רוצה להראות שאפשר לפתור אותה בשתיי דרכים: דרך אחת היא אגף ימין של הזהות, ודרך שנייה היא אגף שמאל של הזהות.
ובכן, דרך אחת לפתור את הבעיה, היא לבחור תחילה m סטודנטים מתוך כלל n הסטודנטים לשמש כחברים במועצת התלמידים.
כע,עבור כל אחד מ- n-m הסטודנטים שלא נבחרו למועצת התלמידים, יש 2 אפשרויות: להיבחר לוועד הכיתתי, או לא להיבחר לוועד הכיתתי - כלומר zz 2^(n-m) zz אפשרויות.
לפי עקרון המכפלה, מספר האפשרויות הכולל הוא : zz (n choose m) 2^(n-m) zz .
נותר לי להראות שאגף ימין גם מהווה פתרון לבעיה שהצגתי, אבל אני קצת מתקשה עם זה...גם לא ממש ברור לי איך אני מתייחס לסיגמה..
מישהו יודע ויכול לעזור??
תודה.
