בחירה עם חשיבות לסדר וללא החזרות

בחלק הקודם ראינו כי מספר הסידורים האפשריים של n עצמים הוא n!. למשל, אם ישנם חמישה כדורים בצבעים שונים ישנם 5! = 120 אפשרויות שונות לסדר אותם בשורה אחת, אחד ליד השני.

בחלק זה נלמד כיצד ניתן לספור את מספר האפשרויות לבחירת k עצמים מתוך n עצמים, כאשר יש חשיבות לסדר בו נבחרו העצמים.

ניתן לשם הדוגמה בעיה הממחישה את המשפט שהובא לעיל. לשמעון 5 כדורים שונים והוא החליט לתת שניים מהם לשני בניו, אחד לכל בן. מהם מספר האפשרויות לחלוקת הכדורים לשני הבנים?

ידוע לנו שיש 120 אפשרויות לסידור 5 הכדורים בשורה אחת. נגדיר שאת הכדור הכי ימני בשורה יקבל בנו הבכור של שמעון ואת הכדור הצמוד לו משמאלו יקבל בנו הצעיר של שמעון. שאר 3 הכדורים יישארו ברשותו של שמעון.

האם יש 120 אפשרויות שונות לחלוקת שני הכדורים לשני הבנים?

בוודאי שלא. מייד נפרט פיתרון לבעיה.

סדר הופעת שני הכדורים הכי ימניים בשורה הוא חשוב, כי מקומו של כדור אחד מסומן עבור הבן הבכור ואילו השני מסומן עבור הבן הצעיר. למשל, הסידור "אדום צהוב ירוק כחול סגול" שונה מהסידור "צהוב אדום ירוק כחול סגול". שני הסידורים שונים כי לפי הסידור הראשון הבן הבכור יקבל את הכדור האדום והבן הצעיר יקבל את הכדור הצהוב, לעומת זאת לפי הסידור השני הבן הבכור יקבל את הכדור הצהוב והצעיר את האדום.

אבל סדר הופעת שלושת הכדורים הנותרים, אלו שלא נבחרו ונשארו לרשותו של שמעון, הוא אינו חשוב. למשל, הסידורים "אדום צהוב ירוק כחול סגול", "אדום צהוב כחול ירוק סגול", "אדום צהוב סגול ירוק כחול" וכן הלאה אינם משנים את התוצאה הסופית שהיא כדור אדום לבן הבכור וכדור צהוב לבן הצעיר.

כלומר, מתוך 120 הסידורים האפשריים לסידור חמשת הכדורים ישנן כפילויות רבות של סידורים שבהן הבחירה של שני הכדורים וחלוקתם לשני הבנים אינה משתנה. כדי למצוא את מספר הסידורים האפשריים לבחירה ולחלוקת שני הכדורים לשני ילדיו של שמעון נצטרך לצמצם ולבטל מתוך 120 הסידורים את אותם סידורים מיותרים החוזרים על עצמם ומציגים שוב ושוב את אותה חלוקה של שני כדורים לשני הבנים.

נציג את ההגעה לפתרון בכמה דרכים.

דרך א'

לבחירת הכדור הראשון, זה המיועד לבן הבכור, ישנן 5 אפשרויות בחירה שונות. הבן הבכור יכול לקבל כדור כלשהו מתוך כל חמשת הכדורים ללא כל הגבלה. כלומר, מספר אפשרויות הבחירה עד כה הוא,

5

לבחירת הכדור השני, זה המיועד לבן הצעיר, נותרו 4 אפשרויות בחירה שונות. הבן הצעיר יכול לקבל כדור רק בבחירה מתוך ארבעת הכדורים שנותרו. נוסיף דרגת בחירה זו לזו הקודמת ונקבל שמספר אפשרויות הבחירה השונות עד כה הוא,

5•4 = 20

וזהו. אין יותר בחירות נוספות. שלושת הכדורים הבאים בתור לא משפיעים ולא תורמים יותר למספר אפשרויות החלוקה השונות של שני הכדורים לשני בניו של שמעון. למשל, אם הכדור הראשון נבחר להיות אדום והשני צהוב אין זה משנה אם השלישי יהיה ירוק, כחול או סגול.

דרך ב'

בתוך חמשת הכדורים נבחין בין שתי תתי-קבוצות. תת-קבוצה אחת מכילה את שני הכדורים שנבחרו לחלוקה לשני הבנים. תת-קבוצה שנייה מכילה את שלושת הכדורים שנשארים אצל שמעון האב. בתת-קבוצה הראשונה חשוב סדר הופעת שני הכדורים, לכן כל התמורות בה הן בעלות משמעות וייחודיות. בתת-קבוצה השנייה נכללים אותם כדורים שלא נבחרו לחלוקה. סדר הופעת הכדורים בתת-קבוצה השנייה אינו חשוב. מספר הצירופים שיש לבטל הוא אם כן מספר הצירופים האפשריים לסידור הכדורים שלא נבחרו והמופיעים בתת-קבוצה השנייה. אם הוספת צירופים נעשית על-ידי מכפלה הרי שביטול הצירופים החוזרים על עצמם מתקבל על-ידי חלוקה. ניקח את מספר הצירופים הכולל ונחלק אותו במספר הצירופים החוזרים על עצמם. נקבל,

5! / (5-2)! = 5!/3! = 5•4 = 20

כלומר ישנם רק 20 סידורים אפשריים לבחירה וחלוקה של שני כדורים לשני הבנים מתוך חמשת הכדורים של שמעון. אפשרות הבחירה נקראת חליפה. חליפה מלשון החלפה, כל אפשרות בחירה שונה דורשת החלפה של או לפחות אחד מהפריטים שנבחרו באלו שלא נבחרו ואו לפחות את סדר בחירת הפריטים שנבחרו.

ננסח משפט באופן כללי. לבחירה עם חשיבות לסדר וללא החזרות של k עצמים מתוך n עצמים יש n!/(n-k)! חליפות שונות.

[לפרק הקודם | לפרק הבא]

[ חזרה לראש העמוד ]

[ עמוד הבית | אודות | זכויות יוצרים | מפת האתר ]