|
|
صفحة: 88
בין n הסדרות דלעיל יש הרבה סדרות שבהן מופיע איבר זה או אחר יותר מפעם אחת . אם נספור רק סדרות שבהן אינ "חזרות" כאלה , נקבל את המשפט הבא : מספר הסדרות בנות k איברים שונים הלקוחים מקבוצה בת n איברים , הוא ו n ( n-l )( n-2 ) - [ n- ( k-l )] אפשר לחזור כאן מילה במילה על ההוכחה של נוסחת מספר התמורות , אלא שמספר השלבים הפעם הוא k ולא וז . ( השלימו את ההוכחה ( . דוגמה ? . אם תייר רוצה לבקר בארבע ערים כלשהן מתוך תשע ערים מסוימות באירופה , מבלי לבקר בשום עיר יותר מפעם אחת , יעמדו לרשותו 9 8 7 6 = 3024 מסלולים אפשריים . הערה : אם , n = k הסדרות שאותן סופרים כאן שוב אינן אלא תמורות ; ואכן , המספר שמתקבל בנוסחה מתלכד במקרה זה עם . 11 ! אם , n < k אינ סדרות באורך k בלי חזרות ו ואמנם , במצב שכזה יופיע 0 בין גורמי הנוסחה , ולכן המכפלה אף היא תהיה . 0 ד . קבוצות חלקיות אחת הנוסחאות החשובות ביותר בקומבינטוריקה היא זו שעונה על השאלה כמה קבוצות שונות בנות k איברים ניתן לבחור מתוך קבוצה נתונה בת n איברים . ( סביר להניח כאן כי , k < n כי אחרת אין ספק שהתשובה לשאלה היא ( . 0 בסעיף שדן בסדרות ענינו על שאלה דומה , ומצאנו שמספר הסדרות בנות k איברים שונים שניתן לבחור מתוך קבוצה בת n איברים , הוא . n ( n-l )( n-2 ) ... [ n- ( k-l )] , ovon שאלנו לא על סדרות בנות k איברים שונים , אלא על קבוצות בנות k איברים ( ונזכור -.בקבוצות , גם בלי שנאמר זאת במפורש , נתכוון לאיברים שונים (! מה ההבדל ? ההבדל הוא שבסדרות גם הסדר קובע . כל קבוצה בת k איברים , מתאימות לה סדרות שונות שבהן אותם k איברים מופיעים בסדרים שונים . בהתאם לנוסחת התמורות , מתאימות לקבוצה בת k איברים בדיוק k ! סדרות שונות . מכאן שמספר הסדרות בנות k איברים שונים שניתן לבחור מתוך קבוצה בת n איברים גדול פי k ! ממספר הקבוצות בנות k איברים שניתן לבחור מתוך אותה קבוצה .
|
|