שלום לכולם, אני מנסה לפתור את השאלה הבאה:
מה מספר האפשרויות לחלק k כדורים זהים ל-2n תאים שונים הממוספרים \{1,2,...,2n\}, כך שלכל i סכום הכדורים בתא ה-i ובתא ה- n+i שונה מ-4?
הלכתי על הכיוון של עקרון הכלה והפרדה אבל נתקעתי בחישוב היעד.
אשמח לעזרה
שלום לכולם, אני מנסה לפתור את השאלה הבאה:
מה מספר האפשרויות לחלק k כדורים זהים ל-2n תאים שונים הממוספרים \{1,2,...,2n\}, כך שלכל i סכום הכדורים בתא ה-i ובתא ה- n+i שונה מ-4?
הלכתי על הכיוון של עקרון הכלה והפרדה אבל נתקעתי בחישוב היעד.
אשמח לעזרה
אתה צודק שצריך להשתמש בעקרון הכלה והפרדה:
עולם: חלוקה של 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) תאים שונים ולכן סה"כ נקבל:
לפיכך מתקיים:
בהצלחה