קומבינטוריקה 5 צירופים עם חזרות ובעיות מתקדמות

קומבינטוריקה

דף 5: צירופים עם חזרות ובעיות מתקדמות

🔁 צירופים עם חזרות

כשבוחרים k פריטים מתוך n סוגים, מותר לבחור אותו סוג יותר מפעם אחת:

\(\binom{n+k-1}{k} = \binom{n+k-1}{n-1}\)

✏️ דוגמה 1: בחירת סוכריות

יש 4 סוגי סוכריות (אדום, כחול, ירוק, צהוב). בכמה דרכים אפשר לבחור 6 סוכריות?

n = 4 סוגים, k = 6 סוכריות, מותר חזרות

\(\binom{4+6-1}{6} = \binom{9}{6} = \binom{9}{3} = \frac{9 \times 8 \times 7}{6} = 84\)

✏️ דוגמה 2: חלוקת כסף

בכמה דרכים אפשר לחלק 10 שקלים (זהים) בין 3 ילדים?

n = 3 ילדים, k = 10 שקלים

\(\binom{3+10-1}{10} = \binom{12}{10} = \binom{12}{2} = 66\)

🎱 שיטת "כדורים ומחיצות" (Stars and Bars)

בעיות מהסוג "לחלק k פריטים זהים ל-n קבוצות"

💡 הרעיון:

מסמנים את הפריטים כ-★ והמחיצות בין הקבוצות כ-|

★★★|★|★★★★ = (3,1,4)

8 כדורים מחולקים ל-3 קבוצות

📐 הנוסחה:

k כדורים ל-n קבוצות = בחירת מיקום ל-(n-1) מחיצות מתוך (k+n-1) מקומות

\(\binom{k+n-1}{n-1} = \binom{k+n-1}{k}\)

✏️ דוגמה 3: בכמה דרכים אפשר לכתוב 12 כסכום של 4 מספרים טבעיים לא-שליליים?

(כלומר: \(x_1 + x_2 + x_3 + x_4 = 12\) כאשר \(x_i \geq 0\))

k = 12, n = 4

\(\binom{12+4-1}{4-1} = \binom{15}{3} = \frac{15 \times 14 \times 13}{6} = 455\)

⚡ כדורים ומחיצות - עם תנאי מינימום

✏️ דוגמה 4: \(x_1 + x_2 + x_3 + x_4 = 12\) כאשר \(x_i \geq 1\)

(כל משתנה חייב להיות לפחות 1)

שיטה: נציב \(y_i = x_i - 1\), אז \(y_i \geq 0\)

\((y_1+1) + (y_2+1) + (y_3+1) + (y_4+1) = 12\)

\(y_1 + y_2 + y_3 + y_4 = 8\)

\(\binom{8+4-1}{3} = \binom{11}{3} = 165\)

📐 נוסחה כללית:

אם \(x_1 + x_2 + ... + x_n = k\) ו-\(x_i \geq m\) לכל i:

\(\binom{k - nm + n - 1}{n-1}\)

👥 חלוקה לקבוצות

סוג 1: קבוצות בגדלים שונים (מתויגות)

✏️ דוגמה 5: 10 תלמידים מתחלקים לקבוצות של 5, 3, 2. כמה דרכים?

\(\binom{10}{5} \times \binom{5}{3} \times \binom{2}{2} = 252 \times 10 \times 1 = 2520\)

סוג 2: קבוצות בגודל שווה (לא מתויגות)

✏️ דוגמה 6: 12 תלמידים מתחלקים ל-3 קבוצות של 4. כמה דרכים?

קודם נחלק כאילו הקבוצות מתויגות:

\(\binom{12}{4} \times \binom{8}{4} \times \binom{4}{4} = 495 \times 70 \times 1 = 34650\)

כעת נחלק ב-3! כי הקבוצות זהות (לא חשוב מי "ראשונה"):

\(\frac{34650}{3!} = \frac{34650}{6} = 5775\)

📐 נוסחה כללית:

n איברים ל-k קבוצות שוות של \(\frac{n}{k}\) איברים:

\(\frac{n!}{\left(\frac{n}{k}\right)!^k \times k!}\)

🧮 מספר פתרונות למשוואות

✏️ דוגמה 7: כמה פתרונות טבעיים (\(x,y,z > 0\)) יש ל:

\(x + y + z = 20\)

כל משתנה ≥ 1, נציב \(x' = x-1, y' = y-1, z' = z-1\)

\(x' + y' + z' = 17\) כאשר \(x',y',z' \geq 0\)

\(\binom{17+3-1}{3-1} = \binom{19}{2} = 171\)

✏️ דוגמה 8: כמה פתרונות שלמים לא-שליליים ל:

\(x + y + z \leq 10\)

שיטה: נוסיף משתנה "slack" w כך ש-\(x + y + z + w = 10\)

כעת יש 4 משתנים ≥ 0 שסכומם 10:

\(\binom{10+4-1}{4-1} = \binom{13}{3} = 286\)

📋 טבלת סיכום - מתי משתמשים במה?

סוג בעיה סדר חשוב? חזרות? נוסחה
תמורה ✓ ✗ \(n!\)
תמורה חלקית ✓ ✗ \(P(n,k) = \frac{n!}{(n-k)!}\)
תמורה עם חזרות ✓ ✓ \(n^k\)
צירוף ✗ ✗ \(\binom{n}{k} = \frac{n!}{k!(n-k)!}\)
צירוף עם חזרות ✗ ✓ \(\binom{n+k-1}{k}\)

💡 טיפים למבחן

כדורים זהים: צירוף עם חזרות

תנאי מינימום: החלף משתנים

קבוצות שוות: חלקו ב-k!

📝 סיכום דף 5

צירוף עם חזרות: \(\binom{n+k-1}{k}\)

כדורים ומחיצות: k פריטים ל-n קבוצות