קומבינטוריקה 2 עצרת ותמורות
קומבינטוריקה
דף 2: עצרת ותמורות
❗ עצרת (Factorial)
n עצרת (מסומן \(n!\)) הוא מכפלת כל המספרים השלמים מ-1 עד n:
\(n! = n \times (n-1) \times (n-2) \times ... \times 2 \times 1\)
📋 דוגמאות:
| n | n! | חישוב |
|---|---|---|
| 0 | 1 | לפי הגדרה |
| 1 | 1 | 1 |
| 2 | 2 | 2 × 1 |
| 3 | 6 | 3 × 2 × 1 |
| 4 | 24 | 4 × 3 × 2 × 1 |
| 5 | 120 | 5 × 4 × 3 × 2 × 1 |
| 6 | 720 | 6 × 5! |
| 10 | 3,628,800 | 10 × 9 × ... × 1 |
💡 תכונה חשובה:
\(n! = n \times (n-1)!\)
דוגמה: 5! = 5 × 4! = 5 × 24 = 120
✏️ חישובים עם עצרת:
\(\frac{8!}{6!} = \frac{8 \times 7 \times 6!}{6!} = 8 \times 7 = 56\)
\(\frac{10!}{8! \times 2!} = \frac{10 \times 9 \times 8!}{8! \times 2} = \frac{90}{2} = 45\)
🔄 תמורה (Permutation)
תמורה = סידור של כל האיברים בסדר מסוים
בתמורה, הסדר חשוב ומשתמשים בכל האיברים
מספר התמורות של n איברים = \(n!\)
✏️ דוגמה 1: סידור אנשים בשורה
בכמה דרכים אפשר לסדר 4 אנשים בשורה?
מקום ראשון: 4 אפשרויות
מקום שני: 3 אפשרויות
מקום שלישי: 2 אפשרויות
מקום רביעי: 1 אפשרות
סה"כ: 4! = 4 × 3 × 2 × 1 = 24 דרכים
✏️ דוגמה 2: סידור ספרים על מדף
בכמה דרכים אפשר לסדר 6 ספרים שונים על מדף?
6! = 720 דרכים
איור: כל התמורות של {A, B, C}
🎯 תמורות עם תנאים
✏️ דוגמה 3: איבר מסוים בקצה
5 אנשים עומדים בשורה. דני חייב להיות ראשון. כמה סידורים?
דני קבוע במקום הראשון
נשאר לסדר 4 אנשים ב-4 מקומות
סה"כ: 4! = 24 דרכים
✏️ דוגמה 4: איבר בקצה כלשהו
5 אנשים בשורה. דני חייב להיות בקצה (ראשון או אחרון). כמה סידורים?
דני יכול להיות במקום 1 או במקום 5: 2 אפשרויות
שאר 4 האנשים: 4! = 24 סידורים
סה"כ: 2 × 4! = 2 × 24 = 48 דרכים
✏️ דוגמה 5: שני איברים צמודים
5 אנשים בשורה. דני ורוני חייבים לעמוד צמודים. כמה סידורים?
שיטה: מתייחסים לדני+רוני כ"יחידה אחת"
יש לנו 4 "יחידות" לסדר: 4! = 24
בתוך היחידה, דני ורוני יכולים להתחלף: 2! = 2
סה"כ: 4! × 2! = 24 × 2 = 48 דרכים
✏️ דוגמה 6: שני איברים לא צמודים
5 אנשים בשורה. דני ורוני לא יכולים לעמוד צמודים. כמה סידורים?
שיטה: משלים
כל הסידורים: 5! = 120
סידורים שהם צמודים: 48 (מדוגמה 5)
סה"כ: 120 - 48 = 72 דרכים
🔁 תמורות עם חזרות
כשיש איברים זהים (חוזרים), מספר התמורות קטן:
\(\frac{n!}{n_1! \times n_2! \times ... \times n_k!}\)
כאשר \(n_1, n_2, ...\) הם מספר החזרות של כל איבר
✏️ דוגמה 7: סידור אותיות עם חזרות
כמה מילים שונות (עם משמעות או בלי) אפשר ליצור מהאותיות של ABBA?
4 אותיות: A מופיעה 2 פעמים, B מופיעה 2 פעמים
\(\frac{4!}{2! \times 2!} = \frac{24}{2 \times 2} = \frac{24}{4} = 6\)
6 מילים: AABB, ABAB, ABBA, BAAB, BABA, BBAA
✏️ דוגמה 8: סידור המילה MISSISSIPPI
11 אותיות: M(1), I(4), S(4), P(2)
\(\frac{11!}{1! \times 4! \times 4! \times 2!} = \frac{39916800}{1 \times 24 \times 24 \times 2} = \frac{39916800}{1152} = 34650\)
💡 למה מחלקים?
כי החלפת איברים זהים ביניהם לא יוצרת סידור חדש.
ב-ABBA, שתי ה-A זהות - החלפתן לא משנה כלום.
⭕ סידור מעגלי
בסידור מעגלי (סביב שולחן עגול), אין "התחלה" ו"סוף".
מספר הסידורים = \((n-1)!\)
✏️ דוגמה 9: 5 אנשים יושבים סביב שולחן עגול. כמה סידורים?
\((5-1)! = 4! = 24\) סידורים
💡 למה (n-1)! ולא n!?
במעגל, סיבוב של כולם מקום אחד נותן את אותו סידור.
לכן "מקבעים" איבר אחד ומסדרים את n-1 הנותרים.
💡 טיפים למבחן
0! = 1 (לפי הגדרה)
צמודים: התייחסו כיחידה
לא צמודים: משלים
חזרות: חלקו בעצרות
📝 סיכום דף 2
עצרת: \(n! = n \times (n-1) \times ... \times 1\)
תמורה (סידור כולם): \(n!\)
עם חזרות: \(\frac{n!}{n_1! \times n_2! \times ...}\)
מעגלי: \((n-1)!\)