הבדלים בין גרסאות בדף "קומבינטוריקה"

נוסף בית אחד ,  לפני 6 חודשים
מ
←‏חליפות: תקלדה
מ (←‏חליפות: תקלדה)
'''חליפות''' - מספר האפשרויות לבחור 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).
פתרון הבעיה נעשה באמצעות "עקרון ההכלה וההפרדה". יש להפחית מסך האפשרויות הכללי את מספר המקרים שבהם אחד מהנמענים מקבל את המכתב המיועד לו. אלא שהפחתה זו מקטינה מדי, שכן הופחתו כל האפשרויות שבהן נמען א' מקבל את מכתבו ובנוסף, כל האפשרויות שבהן נמען ב' מקבל את מכתבו, אולם אפשרויות אלו נחתכות. בחלק מהמקרים גם נמען א' מקבל את מכתבו וגם נמען ב' מקבל את המכתב שנשלח אליו, ואין סיבה לגרוע מקרים אלו פעמיים.
על כן יש להוסיף את מספר המקרים שבהם נמען א' ונמען ב' שניהם מקבלים את מכתביהם, אך זו הוספה מופרזת, משום שכך מונים יתר על המידה את המקרים שבהם נמען א', נמען ב' ונמען ג' מקבלים יחדיו את מכתביהם. לפיכך צריך להוסיף ולהפחית לסירוגין.
 
 
 
423

עריכות