שינויים

88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 9

נוספו 1,544 בתים, 12:13, 20 באוגוסט 2011
/* מבוא לקומבינטוריקה */
'''פתרון.''' למעשה בעייה זו שקולה לבעיית חלוקת 10 אנשים לשתי קבוצות שונות בלבד, מכיוון שיש רק דרך אחת למיין את האנשים לפי הסדר של התור המקורי בכל תת קבוצה. נלמד בהמשך כיצד לפתור בעייה פשוטה זו.
 
 
'''דוגמא.''' בכמה דרכים אפשר לסדר n אנשים בתור?
 
'''פתרון.''' כל אחד יכול להיות ראשון בתור לכן כבר יש n אפשרויות. כעת, נניח ואיציק ראשון בתור, נותר לסדר n-1 אנשים אחריו בתור. נניח באינדוקציה שמספר האפשרויות לסדר n-1 אנשים בתור הוא <math>(n-1)!</math> ונקבל שמספר האפשרויות שלנו הוא <math>n\cdot (n-1)! = n!</math>.
 
 
'''דוגמא.''' בכמה דרכים ניתן לבחור קבוצה של k חפצים מתוך קבוצה של n חפצים? (במילים אחרות, כמה תת קבוצות מעוצמת k יש לקבוצה מגודל n).
 
 
'''פתרון.''' נמיר את הבעייה לבעייה אחרת. נספור את כמות האפשרויות לבחור k חפצים כאשר הסדר בינהם משנה, ולאחר מכן נחלק את הכמות שקיבלנו במספר האפשרויות לסדר את k החפצים (הלא הוא <math>k!</math>).
 
אם כך, אנו מעוניינים לדעת כמה אפשרויות יש לנו לבחור k חפצים מתוך n חפצים כאשר הסדר שלהם משנה. נסדר את n החפצים בשורה וניקח את k הראשונים. כמה פעמים נקבל את אותה סדרת k חפצים? בדיוק כמספר הפעמים שאפשר לסדר את n-k החפצים הנותרים.
 
אם כך, קיבלנו נוסחא <math>{n \choose k} = \frac{n!}{k!(n-k)!}</math>