שאלת מבחן במתמטיקה בדידה - האוניברסיטה העברית 2011 - קומבינטוריקה

בכמה דרכים ניתן לחלק 18 כדורי-כל **זהים** בין 5 קבוצות שונות, אבל ללא שקבוצה כלשהי תקבל יותר מחמישה כדורים?

רמז: השתמשו בהכלה-הפרדה על כוכביות ומחיצות עם האילוץ $x_i \leq 5$.

פתרון: נסמן $x_i$ את מספר הכדורים בקבוצה ה-$i$. צריך למצוא מספר הפתרונות ל: $$x_1 + x_2 + x_3 + x_4 + x_5 = 18, \quad 0 \leq x_i \leq 5$$ נשתמש ב**הכלה-הפרדה**. נגדיר $A_i$ = מספר הפתרונות כש-$x_i \geq 6$. מספר הפתרונות ללא מגבלה עליונה: $\binom{22}{4}$. $|A_i|$: מציבים $y_i = x_i - 6$, נשאר $y_i + \sum_{j\neq i} x_j = 12$, כלומר $\binom{16}{4}$. יש $\binom{5}{1}$ קבוצות כאלה. $|A_i \cap A_j|$: שתי קבוצות עם $\geq 6$, נשאר סכום $6$: $\binom{10}{4}$. יש $\binom{5}{2}$ זוגות. $|A_i \cap A_j \cap A_k|$: שלוש קבוצות עם $\geq 6$, נשאר סכום $0$: $\binom{4}{4} = 1$. יש $\binom{5}{3}$ שלשות. ארבע קבוצות ומעלה: $4 \cdot 6 = 24 > 18$, לכן אין פתרונות. לפי הכלה-הפרדה: $$\binom{22}{4} - \binom{5}{1}\binom{16}{4} - \binom{5}{2}\binom{10}{4} - \binom{5}{3}\binom{4}{4}$$ חישוב: $7315 - 5 \cdot 1820 + 10 \cdot 210 - 10 \cdot 1 = 7315 - 9100 + 2100 - 10 = 305$. התשובה: $305$. $\blacksquare$