גליון 3 — קומבינטוריקה למדעי המחשב

תרגיל 1

תרגיל (1 [א])

עבור הבעיה הבאה:
כמה אפשרויות יש לסידור $n$ אנשים במעגלים כך שאין חשיבות לסדר בין המעגלים אך יש חשיבות לסדר בכל מעגל ואין מעגלים ריקים?
קיבלנו בתרגול את נוסחת הנסיגה $G(n)=nG(n-1),\;\; n\geq 1$ עם תנאי ההתחלה $G(0)=1$ כאשר $G(n)$ מוגדר עבור $n\geq 0$ .

מצאו ביטוי מופרש ל- $G(n)$ עבור $n\geq 0$

נוכיח באינדוקציה כי $G(n)=n!$ .
הוכחה:
בסיס: עבור $n=0$ מתקיים כי $G(0)=0!=1$ . תנאי ההתחלה של $G$ הינו $G(0)=1$ ולכן זה מתקיים.
צעד: נניח כי $G(n)=n!$ ונוכיח כי $G(n+1)=(n+1)!$ .

G(n+1)=(n+1)G(n) \underset{\begin{matrix} \downarrow \\ \R{\text{הנחת האינדוקציה}} \end{matrix}}{=}(n+1)n!=(n+1)!

לכן, לכל $n\geq 0$ מתקיים $G(n)=n!$
∎

תרגיל (1 [ב])

חשבו על פתרון ישיר לבעיה הנותן את התוצאה שיצאה בסעיף א' ללא שימוש בנוסחאות נסיגה או אינדוקציה.

הדרכה: ניתן להגדיר פונקציה חח"ע ועל מקבוצת ערכים $A$ לבחירתכם אל אוסף הפתרונות של הבעיה כך שמתקיים כי $|A|=\alpha$ כאשר $\alpha$ היא התוצאה מסעיף א'. חשוב לשים לב יש להוכיח כי הפונקציה חח"ע ועל ונדרש להוכיח את השוויון $|A|=\alpha$ ולכן פתרון המשתמש באוסף פתרונות של הבעיה בתור $A$ כמובן אינו יקבל ניקוד.
רמז: נסו לחשוב על מיפוי בין כל אדם לבין האדם היושב לידו עם כיוון השעון. האם ההעתקה הזו חח"ע? האם היא על?

הוכחה:
תהי $A$ קבוצת כל הסידורים של $n$ אנשים בשורה ותהי $B$ קבוצת כל הסידורים של $n$ אנשים במעגלים לפי הגדרת השאלה.
נסמן כל אדם באינדקס $1\leq i\leq n$ .
נגדיר פונקציה $f:B\to A$ באופן הבא:

אם אדם $i$ במעגל לבדו, אזי $f(i)=i$
אם אדם $i$ במעגל לא לבד, אזי בהכרח קיים אדם $j$ מימינו. נגדיר $f(i)=j$ .

כאשר $f(i)$ הוא המקום של $i$ בשורה.

נראה כי הפונקציה חח"ע ועל:

חח"ע: נניח בשלילה כי קיימים $1\leq i \neq j \leq n$ כך ש- $f(i)=f(j)$ . נחלק למקרים:
- קיים אדם $1\leq k\leq n$ כך ש- $k \neq i,k \neq j$ ומתקיים $f(i)=f(j)=k$ . אזי, לפי הגדרת $f$ , האדם $i$ עומד משמאל לאדם $k$ וגם האדם $j$ עומד משמאל לאדם $k$ . אך אם $i$ הוא משמאלו של $k$ אז $j$ הוא משמאלו של $i$ ואם $j$ הוא לשמאלו של $k$ אז $i$ הוא לשמאלו של $j$ ולכן בהכרח $f(i)\neq f(j)$ .
- אם $f(i)=f(j)=i$ אזי, לפי הגדרת $f$ אדם $i$ במעגל לבדו, וגם, אדם $i$ נמצא במעגל עם אדם $j$ . אדם אחד לא יכול להיות גם במעגל לבד וגם במעגל עם עוד מישהו ולכן בהכרח $f(i)\neq f(j)$
- באותו האופן עבור $f(i)=f(j)=j$ .
לכן, $f(i)\neq f(j)$ ולכן, לפי הגדרה, $f$ חח"ע.
על: לא יכול להיות מצב בו אדם לא נמצא במעגל: אם הוא לבד, אז קיים מצב לזה ואם הוא לא לבד אז בהכרח יש מישהו מימינו, שכן זה מעגל ולכן לכל אדם יש מישהו שעומד מימנו.
לכן, הפונקציה על.

לכן, מכיוון שיש פונקציה הפיכה מ- $A$ לקבוצת כל הסידורים של אנשים במעגלים, מתקיים כי $|A|$ שווה למספר האפשרויות לסדר $n$ אנשים במעגלים.
הגודל של $A$ הוא בדיוק תמורה של כל האנשים ולכן $|A|=n!$ .
לכן, מספר האפשרויות לסדר $n$ אנשים במעגלים לפי הגדרת השאלה הוא $n!$ .
∎

תרגיל (1 [ג])

יהי $k$ קבוע שלם חיובי נתון. נסמן ב- $G_{k}(n)$ עבור $n\geq 0$ את מספר הדרכים לסדר $n$ אנשים במעגלים ללא חשיבות לסדר בין המעגלים אך עם חשיבות לסדר בכל מעגל כך שבכל מעגל יש לפחות $k$ אנשים.
מצאו נוסחת נסיגה ותנאי התחלה מתאימים ל- $G_{k}(n)$ .

נסתכל על האדם $n$ ונחלק למקרים על בסיס כמות האנשים שנמצאים במעגל של האדם $n$ .

אם $n$ נמצא במעגל שגודלו בדיוק $k$ אז נדרש לבחור לו $k-1$ שותפים אשר יעמדו איתו במעגל. מכיוון שיש $n-1$ אנשים לבחור וזו בחירה בלי חזרות ללא חשיבות לסדר, אזי יש לנו $\begin{pmatrix}n-1 \\ k-1\end{pmatrix}$ דרכים לבחור אותם. כעת, נדרש לסדר את המעגל, לכך יש לנו $(k-1)!$ אפשרויות שכן מיקום האדם הראשון לא משנה. כעת, נשארו לנו $n-k$ אנשים לסדר במעגלים שגודלם $k$ או יותר ולכן זה בדיוק $G_{k}(n-k)$ . לכן, לפי עקרון הכפל, עבור המקרה הזה יש בדיוק $\begin{pmatrix}n-1 \\k-1\end{pmatrix}(k-1)!G_{k}(n-k)=\frac{(n-1)!}{(k-1)!(n-k)!}(k-1)!G_{k}(n-k)=\frac{(n-1)!}{(n-k)!}G_{k}(n-k)$ אפשרויות ליצור את המעגלים.

אם האדם נמצא במעגל עם $k$ אנשים או יותר, נדרש רק לסדר את כל ה- $n-1$ אנשים במעגלים חוקיים, שזה בדיוק $G_{k}(n-1)$ אפשרויות ואז, להוסיף את האדם ה- $n$ לאחד המעגלים לצורך זה יש לנו בכל מעגל אפשרות לשבת ליד כל אחד מהאנשים. יש $n-1$ אנשים ולכן יש לו $n-1$ מקומות לשבת בהם. לכן, לפי עקרון הכפל, במצב הזה יש לבדיוק $(n-1)G_{k}(n-1)$ אפשרויות.

לכן, לפי עקרון הכפל מתקיים:

G_{k}(n)=\frac{(n-1)!}{(n-k)!}G_{k}(n-k)+(n-1)G_{k}(n-1)

עם תנאי ההתחלה: $G_{k}(0)=1$ ובנוסף לכל $1\leq n\leq k-1$ מתקיים $G_{k}(n)=0$ שכן אין מספיק אנשים למעגל אחד.

תרגיל (1 [ד])

מצאו תשובה ישירה לסעיף ג' עבור המקרה בו $k=2$ .

נסתכל על סעיף ב' מחדש ועל הפונקציה $f$ ממנו.
במצב בו $k=2$ לא קיים אדם אשר נמצא במעגל לבד. כלומר, לא קיים $1\leq i \leq n$ כך ש- $f(i)=i$ .
כלומר, בסידור של הקבוצה $A$ נרצה שלא יהיה אף סידור בו קיים אדם $i$ שנמצא במקום ה- $i$ ואז נקבל בדיוק את מספר האפשרויות.
מספר האפשרויות לסידורים כאלו הוא בדיוק $D_{n}$ לאור הנ"ל.
לכן, זהו מספר האפשרויות עבור המקרה $k=2$ .

תרגיל (1 [ה])

נסמן ב- $G_{k,r}(n)$ עבור $n\geq 0$ את מספר הדרכים לסדר $n$ אנשים במעגלים ללא חשיבות לסדר בין המעגלים אך עם חשיבות לסדר בכל מעגל כך שבכל מעגל יש לפחות $k$ אנשים(כולל) ולכל היותר $r$ אנשים(כולל).

מצאו נוסחת נסיגה ותנאי התחלה מתאימים ל- $G_{k,r}(n)$ .

נתבסס על נוסחת הנסיגה מסעיף ג' ונראה כיצד נוכל לתקנה עבור המקרה הזה.
נדרש אם כך, להוריד את כל האפשרויות בהן קיים מעגל המכיל יותר מ- $r$ אנשים, לשם כך, אנו לא צריכים לתקן שום דבר במקרה הראשון, שכן הוא מתעסק עם מעגל של $k$ אנשים שזה מספר קטן או שווה ל- $r$ .
לכן, נתרכז במקרה השני ונראה כיצד נוכל להוריד ממנו את האפשרויות בהן אנו מקבלים מעגל הגדול יותר מ- $r$ .
המקרה השני נותן לנו את כל המעגלים מסודרים על פי הקריטריונים למעט אחד - המעגל בו נמצא האיש $n$ אשר יכול להיות בגודל של $r+1$ שכן אנו מוסיפים אדם אחד לאחד מהמעגלים שסידרנו. לכן, נדרש להוריד את כל האפשרויות בהן קיים מעגל אחד בו $r+1$ אנשים.
מספר האפשרויות שזה יתקיים הוא מספר האפשרויות לסדר מעגל אחד של $r+1$ אנשים ובכך, נבחר $r$ אנשים מתוך $n-1$ , לכך יש בדיוק $\begin{pmatrix}n-1 \\ r\end{pmatrix}$ אפשרויות. לאחר מכן, נסדר את האנשים במעגל ולכך יש בדיוק $r!$ אפשרויות שכן זוהי תמורה של $r$ האנשים שכן המיקום של האיש הראשון במעגל לא משנה, אלא משנה מיקום כל האנשים ביחס אליו. בסוף, נדרש ליצור את שאר המעגלים החוקיים ולכך יש לנו בדיוק $G_{k,r}(n-r-1)$ אפשרויות. לכן לפי עקרון הכפל מספר האפשרויות למקרה הפסול הזה הינו: $\begin{pmatrix}n-1\\r\end{pmatrix}r!G_{k,r}(n-r-1)=\frac{(n-1)!}{r!(n-r-1)!}r!G_{k,r}(n-r-1)=\frac{(n-1)!}{(n-r-1)!}G_{k,r}(n-r-1)$ .
לכן, מספר האפשרויות לסידור $n$ אנשים במעגלים כנדרש בסעיף הינו:

G_{k,r}(n)=\begin{cases} 1 & n=0 \\ 0 & 1\leq n\leq k \\ \frac{(n-1)!}{(n-k)!}G_{k,r}(n-k)+(n-1)G_{k,r}(n-1) & k\leq n\leq r \\ \frac{(n-1)!}{(n-k)!}G_{k,r}(n-k)+(n-1)G_{k,r}(n-1)-\frac{(n-1)!}{(n-r-1)!}G_{k,r}(n-r-1) & r<n \end{cases}

תרגיל (1 [ו])

בסעיפים הבאים ניתן להשתמש בביטוי $G_{k,r}(n)$ .
נתונות $t$ משפחות, בכל משפחה גבר, אישה ו- $d$ ילדים.

בכמה דרכים ניתן לחלק את האנשים למעגלים בגודל $d+2$ ללא חשיבות לסדר בין המעגלים אך עם חשיבות לסדר בכל מעגל כך שבכל מעגל יש גבר, אישה ו- $d$ ילדים - לא בהכרח מאותה משפחה?

יהיו $t$ מעגלים. תחילה נשים בכל מעגל גבר אחד ואז נבחר את האישה לכל מעגל, זוהי תמורה שכן אין חשיבות להאם האישה מאותה משפחה עם הגבר ולכן יש לזה $t!$ אפשרויות.
כעת, נבחר מתוך $t\cdot d$ הילדים את $d$ הילדים לכל מעגל. לכל מעגל יש $d$ ילדים שיהיו בו ולכן, זוהי בחירה של $\begin{pmatrix}t\cdot d\\ d\end{pmatrix}$ למעגל הראשון ואז $\begin{pmatrix}(t-1)d\\ d\end{pmatrix}$ למעגל השני ועד $\begin{pmatrix}d\\ d\end{pmatrix}$ למעגל האחרון. לכן, לבחירות האלו יש:

\begin{pmatrix} td \\ d \end{pmatrix}\begin{pmatrix} (t-1)d \\ d \end{pmatrix}\begin{pmatrix} d \\ d \end{pmatrix}=\frac{(td)!}{d!((t-1)d)!} \frac{((t-1)d)!}{d!((t-2)d)!}\dots \frac{d!}{d!\cdot 0!}=\frac{(td)!}{(d!)^t}

אפשרויות. כעת, בכל מעגל נדרש לסדר את $d+2$ האנשים שיש לנו. נבחר אחד שיהיה המיקום הראשוני ואת השאר נבחר ביחס אליו בתצורת תמורה ולכן זה בדיוק $(d+1)!$ . את פעולה זו אנו עושים ל- $t$ עגלים ולכן, לפי עקרון הכפל: $((d+1)!)^t$ .
לכן, לפי עקרון הכפל, מספר האפשרויות שיש לנו לסדר $t$ משפחות במעגלים בגודל $d+2$ הינן:

t!\cdot \frac{(td)!}{(d!)^t}\cdot ((d+1)!)^t=t!(td)! \left( \frac{(d+1)!}{d!} \right)^t=t!(td)!(d+1)^t

תרגיל (1 [ז])

בכמה דרכים ניתן לחלק את האנשים למעגלים בגודל $d+2$ ללא חשיבות לסדר בין המעגלים, אך עם חשיבות לסדר בכל מעגל כך שלפחות מעגל אחד מכיל משפחה מקורית - כלומר, גבר, אשתו ו- $d$ ילדיהם.

נתחיל בלבחור את המשפחה שתשאר יחדיו. לכך יש לנו $\begin{pmatrix}t \\ 1\end{pmatrix}=t$ אפשרויות בחירה.
כעת, נבצע את אותו הדבר שעשינו ממקודם עבור $t-1$ משפחות שכן כעת מובטח לנו שיהיה מעגל אחד בלבד שמכיל משפחה שלמה ולכן, לזה יהיו $(t-1)!((t-1)d)!(d+1)^{t+1}$ אפשרויות לפי סעיף קודם.
לכן, לפי עקרון הכפל, מספר האפשרויות לסדר את המעגלים לפי נתוני השאלה הינו:

t\cdot (t-1)!((t-1)d)!(d+1)^{t+1}=t!(td-d)!(d+1)^{t+1}

תרגיל 3

תרגיל (3)

נסמן ב- $f(n,k)$ את מספר הדרכים לחלק את $n\geq 1$ ל- $k$ מחוברים אי שליליים שלמים שונים.
לדוגמה, עבור $n=6,k=3$ ניתן לחלק ל- $1+2+3=0+1+5=0+2+4$ ולכן $f(6,3)=3$ .
מצאו נוסחת נסיגה ותנאי התחלה מתאימים ל- $f(n,k)$ עבור $n\geq 0, k\geq 1$ .

נחלק את הבעיה למקרים:

אם $0$ הוא אחד המחוברים, הבעיה שלנו מצטמצמת לפחות מחובר אחד עם אותו ה- $n$ הסופי. זה בדיוק $f(n,k-1)$ .
אם $0$ הוא אינו אחד המחוברים, אנו יודעים שכל המחוברים חיוביים ולכן, אם נחסר מכל אחד מהם אחד, כל המחוברים ישארו אי שליליים. זה מצמצם את הבעיה שלנו שכן כעת יש לנו דרישה לשוויון ל- $n-k$ . זה בדיוק $f(n-k,k)$ אפשרויות.

לכן, נוסחת הנסיגה שלנו הינה:

f(n,k)=f(n,k-1)+f(n-k,k)

עם תנאי ההתחלה:

עבור $n=0,k=0,1$ מתקיים $f(n,k)=1$ .
עבור $n=0,k>0$ מתקיים $f(n,k)=0$ .
עבור $k=0,n=1$ מתקיים $f(n,k)=1$ .
עבור $k=0,n>1$ מתקיים $f(n,k)=0$ .

תרגיל 5

תרגיל (5)

רצף כדורים שחורים ולבנים יקרא $a:b$ מושלם אם הוא מתחיל ומסתיים בכדור לבן ובין כל שני כדורים לבנים יש רצף כדורים שחורים באורך לפחות $a$ ולכל היותר $b$ .
מצאו נוסחת נסיגה ותנאי התחלה למספר הרצפים ה- $a:b$ מושלמים באורך $n$ כאשר נתון כי $b\leq 2a$ .
חשוב לשים לב! $a,b$ נתונים. כלומר, יש להגדיר פונקציה $f(n)$ המשתמשת ב- $a,b$ כקבועים.
ניתן להניח כי $a \neq 0$ .

נחלק למקרים עבור מספר הכדורים השחורים שנמצאים אחרי הכדור הלבן הראשון ונסמנו $i$ . לכל מקרה כזה, נשים בסוף הרצף של הכדורים השחורים כדור לבן אחד ואז, נדרש לבנות רצף $a:b$ מושלם באורך $n-i-1$ שכן הכדור הלבן שסוגר את הבלוק הזה הוא האחד שפותח את ההבא. שזה בדיוק $f(n-i-1)$ .
לכן, נוסחת הנסיגה שלנו היא:

f(n)=\sum_{i=a}^n f(n-i-1)

עם תנאי ההתחלה הבאים:

עבור כדור בודד, הוא יכול להיות לבן ומכיוון שאין שניים, אין תנאים שצריך לקיים ולכן $f(1)=1$ .
עבור $2\leq n\leq a+1$ אין מספיק מקום לרצף יחיד באורך מינימלי של $a+2$ ולכן $f(n)=0$ .
עבור $a+2\leq n\leq b+0$ יש מקום לרצף אחד ולכן $f(n)=1$ .
עבור $b+3\leq n \leq 2a+2$ האורך גדול מדי לרצף אחד אך קטן מידי לשני רצפים ולכן $f(n)=0$ .

תרגיל 7

תרגיל (7)

הוכיחו קומבינטורית:

\begin{pmatrix} r \\ n \end{pmatrix}=\sum_{i=0}^r (-1)^{i}\begin{pmatrix} r \\ i \end{pmatrix}\mathbb{C}_{r}^{n-2i}

הוכחה:
בעיה: כמה אפשרויות יש לחלק $n$ כדורים ל- $r$ תאים שונים כך שבכל תא יהיה מקסימום כדור יחיד.
צד שמאל: נפתור בעיה זו באמצעות הכלה הפרדה.
העולם שלנו יהיה חלוקה של $n$ כדורים ל- $r$ תאים שונים כך שבכל תא יש מספר אי שלילי של כדורים. לכך, לפי משפט, יש בדיוק $W(0)=\mathbb{C}_{r}^n$ אפשרויות.
עבור כל $1\leq i \leq r$ הקבוצה $A_{i}$ תהיה כל האפשרויות לחלק $n$ כדורים ל- $r$ תאים שונים כך שבתא ה- $i$ יש לפחות 2 כדורים.
בבעיה יש סימטריה.
לכן, נסתכל על הגודל של הקבוצה $A_{1}$ . בקבוצה זו, תמיד בתא הראשון יהיו לפחות 2 כדורים. לכן, ישארו לנו לסדר $n-2$ כדורים ב- $r$ תאים, שכן בתא $1$ יש לפחות 2 כדורים. לכן $|A_{1}|=\mathbb{C}_{r}^{n-2}$ .

W(1) \underset{\begin{matrix} \downarrow \\ \R{\text{סימטריה}} \end{matrix}}{=}\begin{pmatrix} n \\ 1 \end{pmatrix}\mathbb{C}_{r}^{n-2}

נסתכל על $W(k)$ עבור $1\leq k\leq r$ :
גודל הקבוצה $A_{1}\cap \dots \cap A_{k}$ היא מספר האפשרויות לחלק $n$ כדורים ל- $r$ תאים שונים כך שבתאים $1,2,\dots,k$ יש כבר $2$ כדורים מתוך ה- $n$ כדורים אך אנו עדיין יכולים להוסיף לתאים אלו עוד כדורים. לכן, נדרש למצוא את מספר האפשרויות לחלק $n-2k$ כדורים זהים ל- $r$ תאים שונים וזה, לפי משפט, בדיוק $\mathbb{C}_{r}^{n-2k}$ . לכן:

W(k) \underset{\begin{matrix} \downarrow \\ \R{\text{סימטריה}} \end{matrix}}{=}\begin{pmatrix} n \\ k \end{pmatrix}\mathbb{C}_{r}^{n-2k}

לכן, לפי הגדרה:

E(0)=\sum_{i=1}^r (-1)^i \begin{pmatrix} n \\ i \end{pmatrix}\mathbb{C}_{r}^{n-2i}

וזהו הפתרון לבעיה.
צד ימין: מכיוון שבכל תא יש מקסימום כדור אחד, אחרי שבחרנו תא לא נוכל לבחור בו שוב. לכן, זוהי בחירה של $n$ איברים מתוך $r$ בלי חזרות ושהסדר אינו חשוב. לכן, זה בדיוק $\begin{pmatrix}r \\ n\end{pmatrix}$ .

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

\begin{pmatrix} r \\ n \end{pmatrix}=\sum_{i=0}^r (-1)^i \begin{pmatrix} r \\ i \end{pmatrix}\mathbb{C}_{r}^{n-2i}

∎