תרגילים - בדידה 2

בוחרים 3 מקומות מתוך 8 עבור $A$: $\binom{8}{3}$ דרכים. ב-5 המקומות הנותרים ממקמים $B$ או $C$: $2^5$ דרכים.

$\binom{8}{3} \cdot 2^5 = 56 \cdot 32 = 1792$

כדורים ומחיצות: $k = 15$ כדורים, $n = 4$ קופסאות.

$\binom{15 + 4 - 1}{15} = \binom{18}{15} = \binom{18}{3} = 816$

נשתמש בהכלה והדחה. סה"כ תמורות: $6!$

• $|A_1|$ = תמורות שבהן 1 במקום הראשון: $5!$
• $|A_2|$ = תמורות שבהן 2 במקום השני: $5!$
• $|A_1 \cap A_2|$ = 1 במקום ראשון וגם 2 במקום שני: $4!$

$6! - 5! - 5! + 4! = 720 - 120 - 120 + 24 = 504$

בוחרים 3 מתוך 10 לקבוצה ראשונה, 3 מתוך 7 לשנייה, והשאר לשלישית. כיוון ששתי הקבוצות בגודל 3 אינן מסומנות, מחלקים ב-$2!$:

$\frac{\binom{10}{3}\binom{7}{3}\binom{4}{4}}{2!} = \frac{120 \cdot 35 \cdot 1}{2} = 2100$

אגף שמאל: מספר הדרכים לבחור 2 איברים מקבוצה $S$ בגודל $2n$.

אגף ימין: נחלק את $S$ לשתי קבוצות זרות $A, B$ בגודל $n$ כל אחת.

• $\binom{n}{2}$ — שני האיברים מ-$A$
• $\binom{n}{2}$ — שני האיברים מ-$B$
• $n^2$ — איבר אחד מ-$A$ ואחד מ-$B$ (כלל הכפל)

סה"כ: $2\binom{n}{2} + n^2$. $\blacksquare$

לפי זהות ונדרמונד עם $m = n$ ו-$r = n$:

$\sum_{k=0}^{n} \binom{n}{k}\binom{n}{n-k} = \binom{2n}{n}$

מסימטריה $\binom{n}{n-k} = \binom{n}{k}$, ולכן:

$\sum_{k=0}^{n}\binom{n}{k}^2 = \binom{2n}{n}$

לפי זהות הבליעה: $k\binom{n}{k} = n\binom{n-1}{k-1}$, ולכן:

$\sum_{k=0}^{n}(-1)^k k \binom{n}{k} = n \sum_{k=1}^{n}(-1)^k \binom{n-1}{k-1} = n \sum_{j=0}^{n-1}(-1)^{j+1}\binom{n-1}{j}$

$= -n \sum_{j=0}^{n-1}(-1)^j\binom{n-1}{j} = -n \cdot (1-1)^{n-1} = 0$

לכל מספר שלם יש שארית מחלוקה ב-5 מתוך $\{0, 1, 2, 3, 4\}$ — 5 שובכים. יש 6 מספרים (יונים). לפי שובך היונים, לפחות שניים חולקים את אותה שארית, וההפרש ביניהם מתחלק ב-5. $\blacksquare$

נחלק את הריבוע ל-4 ריבועים קטנים בגודל $\frac{1}{2} \times \frac{1}{2}$. 5 נקודות ב-4 ריבועים — לפי שובך היונים, לפחות שתי נקודות באותו ריבוע קטן. האלכסון של ריבוע $\frac{1}{2} \times \frac{1}{2}$ הוא $\frac{\sqrt{2}}{2}$, ולכן המרחק ביניהן קטן מ-$\frac{\sqrt{2}}{2}$. $\blacksquare$

כל מספר $m \in \{1, \ldots, 2n\}$ ניתן לכתוב כ-$m = 2^s \cdot q$ כאשר $q$ אי-זוגי. ב-$\{1, \ldots, 2n\}$ יש $n$ מספרים אי-זוגיים, כלומר $n$ ערכים אפשריים ל-$q$ — אלה השובכים. $n+1$ מספרים ב-$n$ שובכים — לפי שובך היונים, שניים חולקים את אותו $q$: נניח $a = 2^s q$ ו-$b = 2^t q$ עם $s < t$, אז $a \mid b$. $\blacksquare$

$|A_2| = \lfloor 1000/2 \rfloor = 500$, $|A_3| = 333$, $|A_5| = 200$.

$|A_2 \cap A_3| = \lfloor 1000/6 \rfloor = 166$, $|A_2 \cap A_5| = 100$, $|A_3 \cap A_5| = 66$.

$|A_2 \cap A_3 \cap A_5| = \lfloor 1000/30 \rfloor = 33$.

$|A_2 \cup A_3 \cup A_5| = 500 + 333 + 200 - 166 - 100 - 66 + 33 = 734$

אינם מתחלקים: $1000 - 734 = 266$.

לפי הנוסחה:

$D_5 = 5!\sum_{k=0}^{5}\frac{(-1)^k}{k!} = 120\left(1 - 1 + \frac{1}{2} - \frac{1}{6} + \frac{1}{24} - \frac{1}{120}\right)$

$= 120 \cdot \frac{60 - 60 + 30 - 10 + 2.5 - 0.5}{60}$

נחשב בדיוק: $120 \left(\frac{1}{2} - \frac{1}{6} + \frac{1}{24} - \frac{1}{120}\right) = 60 - 20 + 5 - 1 = 44$

לפי הכלה והדחה, מספר הפונקציות על מ-$[n]$ ל-$[k]$:

$\sum_{j=0}^{k}(-1)^j \binom{k}{j}(k-j)^n$

עם $n = 5, k = 3$:

$\binom{3}{0}\cdot 3^5 - \binom{3}{1}\cdot 2^5 + \binom{3}{2}\cdot 1^5 = 243 - 96 + 3 = 150$

משוואה אופיינית: $x^2 - 5x + 6 = 0 \Rightarrow (x-2)(x-3) = 0$.

שורשים: $r_1 = 2, r_2 = 3$. פתרון כללי: $a_n = \alpha \cdot 2^n + \beta \cdot 3^n$.

תנאי התחלה:

• $a_0 = \alpha + \beta = 1$
• $a_1 = 2\alpha + 3\beta = 4$

$\Rightarrow \beta = 2, \alpha = -1$.

$a_n = -2^n + 2 \cdot 3^n$

משוואה אופיינית: $x^2 - 4x + 4 = 0 \Rightarrow (x-2)^2 = 0$.

שורש כפול $r = 2$. פתרון כללי: $a_n = (\alpha + \beta n) \cdot 2^n$.

• $a_0 = \alpha = 1$
• $a_1 = (\alpha + \beta) \cdot 2 = 6 \Rightarrow \alpha + \beta = 3 \Rightarrow \beta = 2$

$a_n = (1 + 2n) \cdot 2^n$

אם המחרוזת מתחילה ב-1, ממשיכים עם מחרוזת חוקית באורך $n-1$. אם מתחילה ב-0, התו הבא חייב להיות 1, וממשיכים עם מחרוזת חוקית באורך $n-2$.

$a_n = a_{n-1} + a_{n-2}, \quad a_1 = 2, \; a_2 = 3$

זהו בדיוק $a_n = F_{n+2}$ (מספרי פיבונאצ'י).

עץ על $n$ קודקודים מכיל $n-1$ צלעות. עץ על 6 קודקודים מכיל 5 צלעות. גרף קשיר וחסר מעגלים על 6 קודקודים — לכל היותר 5 צלעות. יער (גרף חסר מעגלים, לא בהכרח קשיר) על 6 קודקודים — לכל היותר 5 צלעות. 7 צלעות > 5, ולכן הגרף מכיל מעגל. $\blacksquare$

כיוון $\Rightarrow$: נניח $G$ דו-צדדי עם חלוקה $(A, B)$. כל מעגל מתחלף בין $A$ ו-$B$, ולכן חייב לחזור לצד ההתחלתי — אורך זוגי.

כיוון $\Leftarrow$: נניח $G$ קשיר וללא מעגל אי-זוגי. נבחר קודקוד $v$ ונגדיר: $A$ = קודקודים במרחק זוגי מ-$v$, $B$ = מרחק אי-זוגי. אם קיימת צלע בתוך $A$ (בין $u, w$ עם $d(v,u), d(v,w)$ זוגיים), נקבל מעגל באורך אי-זוגי — סתירה. $\blacksquare$

לפי משפט קיילי: $4^{4-2} = 4^2 = 16$ עצים.

ניתן לאמת: קודי פרופר האפשריים הם כל הסדרות באורך 2 מעל $\{1,2,3,4\}$: $(1,1), (1,2), (1,3), (1,4), (2,1), \ldots, (4,4)$ — סה"כ $4^2 = 16$.

חסם עליון ($R(3,3) \leq 6$): נצבע את צלעות $K_6$ באדום וכחול. לקודקוד $v$ יש $\deg(v) = 5$ שכנים. לפי שובך היונים, לפחות 3 צלעות מאותו צבע — נניח 3 צלעות אדומות ל-$u_1, u_2, u_3$. אם צלע כלשהי בין $u_i, u_j$ אדומה — משולש אדום. אחרת, כל 3 הצלעות ביניהם כחולות — משולש כחול.

חסם תחתון ($R(3,3) > 5$): נצבע את $K_5$ כמעגל $C_5$ אדום ו-$\overline{C_5}$ (מחומש פנימי) כחול. בצביעה זו אין משולש מונוכרומטי. $\blacksquare$