מספר האפשרויות לחלק כדורים זהים לתאים עם תנאים מיוחדים

שלום לכולם, אני מנסה לפתור את השאלה הבאה:

מה מספר האפשרויות לחלק k כדורים זהים ל-2n תאים שונים הממוספרים \{1,2,...,2n\}, כך שלכל i סכום הכדורים בתא ה-i ובתא ה- n+i שונה מ-4?

הלכתי על הכיוון של עקרון הכלה והפרדה אבל נתקעתי בחישוב היעד.
אשמח לעזרה :slight_smile:

אתה צודק שצריך להשתמש בעקרון הכלה והפרדה:

עולם: חלוקה של k כדורים זהים ב-2n תאים שונים ולכן W(0)=CC_{2n}^{k}.
תכונות: יהיו n תכונות רעות, כאשר משמעות תכונה p_{i} היא שסכום הכדורים בתא ה-i ובתא ה-n+i שווה ל-4.
יעד: מאחר ומדובר בתכונות רעות, עלינו למצוא את E(0).
נשים לב כי אם סכום הכדורים בשני התאים n+i ו-i שווה ל-4 אז יש 5 אפשרויות לחלק את הכדורים בהתאמה. נניח כי r תכונות מתקיימות ולכן r זוגות של תאים מכילים 4 כדורים לכל זוג. נותר לחלק k-4r כדורים זהים ב-2(n-r) תאים שונים ולכן סה"כ נקבל:

W(p_{1},...,p_{r})=CC_{2(n-r)}^{k-4r}\cdot5^{r}\Rightarrow W(r)={n \choose r}\cdot CC_{2(n-r)}^{k-4r}\cdot5^{r}

לפיכך מתקיים:

E(0)=\sum_{r=0}^{n}(-1)^{r}\cdot W(r)=\sum_{r=0}^{r}(-1)^{r}\cdot{n \choose r}\cdot CC_{2(n-r)}^{k-4r}\cdot5^{r}

בהצלחה :slight_smile: