קומבינטוריקה – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מ ←חליפות: תקלדה |
|||
שורה 15:
'''חליפות''' - מספר האפשרויות לבחור k עצמים מתוך n עצמים שונים, עם חשיבות לסדר הבחירה.
לדוגמה, מספר הדרכים לשים k כדורים שונים בתוך n תאים שונים, כשבכל תא מקום לכדור אחד בלבד (כאן בוחרים k תאים, עבור כל כדור, מתוך n תאים). הנוסחה היא <math>{n! \over (n-k)!}</math> או <math>nPr</math> כש-r מציין את k, ולפעמים <math>(n)_k</math>
'''חליפות עם חזרות''' - מספר האפשרויות לבחור k עצמים מתוך n עצמים שונים, עם חשיבות לסדר וכשיש אפשרות לחזרות (ייתכן ש-k גדול מ-n).
שורה 45:
פתרון הבעיה נעשה באמצעות "עקרון ההכלה וההפרדה". יש להפחית מסך האפשרויות הכללי את מספר המקרים שבהם אחד מהנמענים מקבל את המכתב המיועד לו. אלא שהפחתה זו מקטינה מדי, שכן הופחתו כל האפשרויות שבהן נמען א' מקבל את מכתבו ובנוסף, כל האפשרויות שבהן נמען ב' מקבל את מכתבו, אולם אפשרויות אלו נחתכות. בחלק מהמקרים גם נמען א' מקבל את מכתבו וגם נמען ב' מקבל את המכתב שנשלח אליו, ואין סיבה לגרוע מקרים אלו פעמיים.
על כן יש להוסיף את מספר המקרים שבהם נמען א' ונמען ב' שניהם מקבלים את מכתביהם, אך זו הוספה מופרזת, משום שכך מונים יתר על המידה את המקרים שבהם נמען א', נמען ב' ונמען ג' מקבלים יחדיו את מכתביהם. לפיכך צריך להוסיף ולהפחית לסירוגין.
| |||