סידור n עצמים
בפרקים הקודמים למדנו על ייצוג הסתברות בעזרת שבר, על פעולת החיבור בין הסתברויות בלתי-תלויות, על פעולת הכפל בין הסתברויות תלויות וגם על עץ ההסתברויות. בפרק זה ובפרקים הבאים נלמד על הקומבינטוריקה.
קומבינטוריקה הנו ענף מתמטי העוסק במניית איבריה של קבוצה סופית וברת מנייה של מספרים בדידים. דוגמה נפוצה לכך היא מניית מספר הסידורים (קומבינציות) האפשריים של מספר עצמים וחלוקתם לקבוצות.
לשם המחשה ראשונית של מהות הקומבינטוריקה נבחן את הבעיה הפשוטה הבאה. שק מכיל ארבע כדורים בצבעים שונים: צהוב, ירוק, כחול וסגול. מוציאים מתוך השק את ארבעת הכדורים, כדור אחר כדור. כמה אפשרויות שונות של סדר הוצאה של הכדורים קיימות?
בעיה זו מגדירה בתוכה, בהיחבא, בעיה של בחירת סידור מסוים מתוך סך סידורים אפשריים. הסדר הנחבא בהגדרת הבעיה הוא סדר הוצאת הכדורים מתוך השק. לפני שנפתור את הבעיה נדון קודם במספר הסידורים האפשריים ובהסתברות להתממשות סידור מסוים.
בשק ישנם ארבעה כדורים. לכל כדור הסתברות שווה להישלף מתוך השק. אם נמספר את הכדורים מאחד עד ארבע נוכל לרשום את סך כל הסידורים האפשריים של הכדורים לפי סדר הוצאתם מהשק. הנה כך,
| מספר סידור | כדור ראשון | כדור שני | כדור שלישי | כדור רביעי |
|---|---|---|---|---|
| 1 | 1 | 2 | 3 | 4 |
| 2 | 1 | 2 | 4 | 3 |
| 3 | 1 | 3 | 2 | 4 |
| 4 | 1 | 3 | 4 | 2 |
| 5 | 1 | 4 | 2 | 3 |
| 6 | 1 | 4 | 3 | 2 |
| 7 | 2 | 1 | 3 | 4 |
| 8 | 2 | 1 | 4 | 3 |
| 9 | 2 | 3 | 1 | 4 |
| 10 | 2 | 3 | 4 | 1 |
| 11 | 2 | 4 | 1 | 3 |
| 12 | 2 | 4 | 3 | 1 |
| 13 | 3 | 1 | 2 | 4 |
| 14 | 3 | 1 | 4 | 2 |
| 15 | 3 | 2 | 1 | 4 |
| 16 | 3 | 2 | 4 | 1 |
| 17 | 3 | 4 | 1 | 2 |
| 18 | 3 | 4 | 2 | 1 |
| 19 | 4 | 1 | 2 | 3 |
| 20 | 4 | 1 | 3 | 2 |
| 21 | 4 | 2 | 1 | 3 |
| 22 | 4 | 2 | 3 | 1 |
| 23 | 4 | 3 | 1 | 2 |
| 24 | 4 | 3 | 2 | 1 |
סך הכול ישנם 24 סידורי הוצאה שונים של ארבעת הכדורים השונים מתוך השק. ניתן להגיע למספר זה גם בדרך פחות מייגעת מהטבלה שלעיל.
ישנם ארבעה כדורים בתוך השק. הבחירה של הכדור הראשון שיצא מתוך השק היא חופשית. הכדור הראשון לצאת מתוך השק יכול להיות כל אחד מארבעת הכדורים שבו. לכן מספר האפשרויות לבחירת הכדור הראשון הוא 4. הבחירה של הכדור השני שיצא מהשק היא בחירה של כדור אחד מתוך שלושת הכדורים שנותרו בו. לכן מספר האפשרויות לבחירת הכדור השני הוא 3. הבחירה של הכדור השלישי שיצא מהשק היא בחירה של כדור אחד מתוך שני הכדורים שנותרו בו. לכן מספר האפשרויות לבחירת הכדור השלישי הוא 2. אחרי הוצאתם של שלושה כדורים מתוך השק נותר בו רק כדור אחד. כעת אין עוד אפשרות לבחירה בין מספר כדורים, מספר האפשרויות לבחירת הכדור הרביעי הוא 1. הכדור הרביעי שיצא מהשק הוא בהכרח הכדור שנותר בו.
מכאן שסך האפשרויות לסדר הוצאת הכדורים מתוך השק הוא,
24 =
סך מספר הסידורים של 4 כדורים
נשים לב שכמות הערכים המוכפלים אחד בשני הוא ככמות העצמים (כדורים בדוגמה שלנו) המופיעים בסידור. כל הגדלה של מספר העצמים תגדיל את מספר הערכים המוכפלים. למשל, אם יהיו חמישה כדורים בתוך השק, אז לבחירת הכדור הראשון יהיו 5 אפשרויות, לבחירת הכדור השני היו 4 אפשרויות וכו'.
צורת הרישום המקוצרת שמספקת פעולת העצרת שימושית מאוד בתחום הקומבינטוריקה. את הביטוי החשבוני שלעיל ניתן לרשום גם כך.
4! =
סך מספר הסידורים של 4 כדורים
כל אפשרות סידור ייחודית נקראת בשם תמורה (תמורה מלשון שינוי, כל סידור מכיל שינוי כלשהו לעומת כל אחד מהסידורים האחרים). בדוגמה שלעיל ישנן 24 תמורות שונות.
ניסוח כללי של המשפט שנלמד בחלק זה הוא, אפוא, לסידור n עצמים שונים יש n! תמורות שונות.
[ עמוד ראשי - קלקולוס | הסתברות וקומבינטוריקה : ייצוג הסתברות בעזרת שברים | חיבור הסתברויות | הכפלת הסתברויות | עץ הסתברויות | עצרת | סידור n עצמים | בחירה עם חשיבות לסדר וללא החזרות | בחירה עם חשיבות לסדר ועם החזרות | בחירה ללא חשיבות לסדר וללא החזרות | סיכום כללי הקומבינטוריקה | מקדם הבינום | משולש פסקל | הבינום של ניוטון ]