קומבינטוריקה 4 צירופים
קומבינטוריקה
דף 4: צירופים
🎯 מהו צירוף?
צירוף = בחירה של k איברים מתוך n איברים, כאשר הסדר לא חשוב
סימונים: \(\binom{n}{k}\) או \(C(n,k)\) או \(_nC_k\)
💡 ההבדל העיקרי:
תמורה
הסדר חשוב
{A,B} ≠ {B,A}
צירוף
הסדר לא חשוב
{A,B} = {B,A}
📐 הנוסחה
\(\binom{n}{k} = \frac{n!}{k!(n-k)!}\)
💡 הסבר הנוסחה:
\(\binom{n}{k} = \frac{P(n,k)}{k!}\)
מחלקים את התמורה החלקית ב-k! כי לא אכפת לנו מהסדר
(כל קבוצה של k איברים נספרה k! פעמים בתמורה)
✏️ דוגמה לחישוב:
\(\binom{5}{2} = \frac{5!}{2! \times 3!} = \frac{120}{2 \times 6} = \frac{120}{12} = 10\)
דרך מקוצרת:
\(\binom{5}{2} = \frac{5 \times 4}{2 \times 1} = \frac{20}{2} = 10\)
✏️ דוגמאות
דוגמה 1: בחירת ועדה
בכמה דרכים אפשר לבחור ועדה של 3 אנשים מתוך 10?
הסדר לא חשוב (ועדה של {א,ב,ג} = ועדה של {ג,ב,א})
\(\binom{10}{3} = \frac{10 \times 9 \times 8}{3 \times 2 \times 1} = \frac{720}{6} = 120\)
דוגמה 2: בחירת קלפים
בכמה דרכים אפשר לבחור 5 קלפים מחפיסת 52?
\(\binom{52}{5} = \frac{52!}{5! \times 47!} = \frac{52 \times 51 \times 50 \times 49 \times 48}{120} = 2,598,960\)
דוגמה 3: בחירת פירות
בסלסלה 8 פירות שונים. כמה דרכים לבחור 3 פירות?
\(\binom{8}{3} = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = \frac{336}{6} = 56\)
📋 תכונות חשובות
| תכונה | נוסחה | דוגמה |
|---|---|---|
| סימטריה | \(\binom{n}{k} = \binom{n}{n-k}\) | \(\binom{10}{3} = \binom{10}{7}\) |
| בחירת 0 | \(\binom{n}{0} = 1\) | \(\binom{5}{0} = 1\) |
| בחירת הכל | \(\binom{n}{n} = 1\) | \(\binom{5}{5} = 1\) |
| בחירת 1 | \(\binom{n}{1} = n\) | \(\binom{5}{1} = 5\) |
| זהות פסקל | \(\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}\) | \(\binom{5}{2} = \binom{4}{1} + \binom{4}{2}\) |
| סכום שורה | \(\sum_{k=0}^{n}\binom{n}{k} = 2^n\) | \(\binom{3}{0}+\binom{3}{1}+\binom{3}{2}+\binom{3}{3}=8\) |
💡 הסבר תכונת הסימטריה:
לבחור k איברים = לבחור n-k איברים שלא לקחת
לכן \(\binom{10}{3} = \binom{10}{7} = 120\)
🔺 משולש פסקל
משולש פסקל מכיל את כל ערכי הצירופים:
💡 קריאת המשולש:
שורה n מכילה את \(\binom{n}{0}, \binom{n}{1}, ..., \binom{n}{n}\)
דוגמה: שורה 4: \(\binom{4}{0}=1, \binom{4}{1}=4, \binom{4}{2}=6, \binom{4}{3}=4, \binom{4}{4}=1\)
🎯 דוגמאות מורכבות
דוגמה 4: ועדה עם תנאי
מ-6 גברים ו-4 נשים, בכמה דרכים אפשר לבחור ועדה של 5 אנשים עם לפחות 2 נשים?
מקרה 1: 2 נשים + 3 גברים
\(\binom{4}{2} \times \binom{6}{3} = 6 \times 20 = 120\)
מקרה 2: 3 נשים + 2 גברים
\(\binom{4}{3} \times \binom{6}{2} = 4 \times 15 = 60\)
מקרה 3: 4 נשים + 1 גבר
\(\binom{4}{4} \times \binom{6}{1} = 1 \times 6 = 6\)
סה"כ: 120 + 60 + 6 = 186 דרכים
דוגמה 5: בחירת אלכסונים במצולע
כמה אלכסונים יש במשושה (6 צלעות)?
סה"כ קטעים בין 6 קודקודים: \(\binom{6}{2} = 15\)
פחות 6 צלעות = 15 - 6 = 9 אלכסונים
נוסחה כללית: \(\frac{n(n-3)}{2}\) = \(\frac{6 \times 3}{2} = 9\) ✓
דוגמה 6: נתיבים ברשת
כמה נתיבים קצרים ביותר מ-(0,0) ל-(4,3) כשאפשר ללכת רק ימינה או למעלה?
צריך 4 צעדים ימינה (י) ו-3 צעדים למעלה (מ)
סה"כ 7 צעדים, בוחרים 3 מהם להיות "למעלה" (או 4 להיות "ימינה")
\(\binom{7}{3} = \binom{7}{4} = \frac{7 \times 6 \times 5}{3 \times 2 \times 1} = 35\)
💡 טיפים למבחן
הסדר לא חשוב → צירוף
סימטריה: \(\binom{n}{k}=\binom{n}{n-k}\)
"לפחות": פרקו למקרים
📝 סיכום דף 4
\(\binom{n}{k} = \frac{n!}{k!(n-k)!}\)
צירוף = בחירה ללא חשיבות לסדר