6+7 - עקרון ההכלה-הפרדה ופונקציות יוצרות — קומבינטוריקה למדעי המחשב

הכלה והפרדה

יש לנו איזשהו עולם אשר לו נקרא $\Omega$ ובתוך העולם יש לנו תכונות $A_{1},A_{2},A_{3}$ .
כל תכונה היא פשוט תת קבוצה של העולם. כלומר $A_{1},A_{2},A_{3} \subseteq \Omega$ .
מה שאנו רוצים לחשב את כל האיברים המקימים או לפחות תכונה אחת או אף תכונה.
ראינו בהרצאה כי כל האיברים שלא מקיימים אף תכונה נקראים $E(0)$ וכל האיברים המקיימים לפחות תכונה אחת נקראים $W(0)-E(0)$ .

E(0)=\sum_{r=0}^{\R{\text{כמות התכונות}}} (-1)^r W(r)

כאשר $W(r)=\begin{matrix}\R{\text{סכום כל החיתוכים}}\\ \R{\text{של r תכונות}}\end{matrix}$ .
כלומר, עבור $A_{1},A_{2},A_{3}$ מתקיים:

W(1)=|A_{1}|+|A_{2}|+|A_{3}|

W(2)=|A_{1}\cap A_{2}|+|A_{1} \cap A_{3}|+|A_{2} \cap A_{3}|

W(3)=|A_{1}\cap A_{2}\cap A_{3}|

תבנית פתרון עם הכלה-הפרדה

עולם
תכונות
מה מחפשים? $E(0)/W(0)-E(0)$
סימטריה(חיתוך של כל $t$ תכונות זהה.) - כן או לא? (הדבר היחיד שלא צריך לנמק בקורס)
חישוב $W(r)$
הצבה

תרגול

תרגיל

כמה פתרונות קיימים למשוואה: $x_{1}+x_{2}+x_{3}+x_{4}+x_{5}+x_{6}=20$ כך שלכל $i$ מתקיים $0\leq x_{i}\leq 8$ ?

(1) עולם: כמה פתרונות קיימים למשוואה הנ"ל כל ש- $x_{i}\geq 0$ . זה בדיוק $\mathbb{C}_{6}^{20}$ .
(2) תכונות:
א. $0\leq x_{i}\leq 8$ ⇐ זה מה שאנחנו רוצים בסוף.
ב. $x_{i}>8$ עבור $1\leq i \leq 6$ ⇐ נשתמש בתכונה הזו בלבד לעקרון הכלה-הפרדה.

(3) מה מחפשים? $E(0)$ . כלומר, כל פתרונות שלא מקיימים אף תכונה. כלומר, לכל $i$ לא מתקיים $x_{i}>8$ ולכן $0\leq x_{i}\leq 8$ .

(4) סימטריה: יש סימטריה!

(5) חישוב $W$ -ים עבןר $0\leq r\leq 6$ .

W(1)=|A_{1}|+|A_{2}|+|A_{3}|+|A_{4}|+\dots+|A_{6}|

כל קבוצה $A_{i}$ מסמלת את כל הפתרונות שבהן $x_{i}$ גדול מ- $8$ . ולכן $|A_{i}|=\mathbb{C}_{6}^{20-9}$ . (למה אנחנו לא מורידים את כמות התאים ל- $5$ ? כי יכול להיות שהוא גדול יותר ואז יש משלים)
לאור הסימטריה נקבל:

W(1)=\begin{pmatrix} 6 \\ 1 \end{pmatrix}|A_{1}|=\begin{pmatrix} 6 \\ 1 \end{pmatrix}\mathbb{C}_{6}^{11}

כעת נמשיך:

W(2)\underset{\begin{matrix} \downarrow \\ \R{\text{סימטריה}} \end{matrix}}{=}\begin{pmatrix} 6 \\ 2 \end{pmatrix}|A_{1}\cap A_{2}|

נמצא את מספר הפתרונות כך ש- $x_{1}\geq 9,x_{2}\geq 9$ שזה בדיוק $|A_{1}\cap A_{2}|$ .
נכניס $9$ לתא הראשון ואז $9$ לתא השני ואת השאר נבחר כך:

|A_{1}\cap A_{2}|=\mathbb{C}_{6}^{20-9-9}=\mathbb{C}_{6}^{2}

לכן:

W(2)=\begin{pmatrix} 6 \\ 2 \end{pmatrix}\mathbb{C}_{6}^2

כעת, עבור $3\leq r\leq 6$ מתקיים $W(r)=0$ שכן אם שלושה משתנים גדולים מ- $9$ אזי הסכום הוא לפחות $29$ וזוהי סתירה לכך שהסכום הוא $20$ .

E(0)=\sum_{r=0}^{6} (-1)^{r}W(r)=W(0)-W(1)+W(2)=\mathbb{C}_{6}^{20}-\begin{pmatrix} 6 \\ 1 \end{pmatrix}\mathbb{C}_{6}^{11}+\begin{pmatrix} 6 \\ 2 \end{pmatrix}\mathbb{C}_{6}^2

וזוהי התשובה.

תרגיל

בכמה דרכים ניתן לסדר את המספרים $1,1,1,2,2,2,3,3,3$ כך שיווצר לפחות רצף אחד של $3$ מספרים זהים?

נותנים לנו $9$ מספרים ורוצים שנסדר אותם. כלומר, נקבל מילה באורך $9$ שבה נרצה לפחות רצף אחד של $3$ מספרים זהים.
אם היינו מנסים לפתור את זה בצורה ישירה, אז או שלא היינו סופרים את כל המקרים או שהיו לנו כפילויות.
לכן, נשתמש בהכלה-הפרדה.

(1) עולם: סידור של $1,1,1,2,2,2,3,3,3$ . יש לנו $9!$ לסדר $9$ מספרים ואז $3!$ לכל מספר שכן כל המספרים הזהים זהים ולכן, נקבל כי גודל העולם שלנו הוא $W(0)=\frac{9!}{3!\cdot 3!\cdot 3!}$ .
(2) תכונות עבור $1\leq i\leq 3$ :

$A_{i}$ - קיים הרצף $iii$
$A_{i}$ - לא קיים הרצף $iii$

אנחנו נבחר את האופציה הראשונה שכן קל יותר לעבוד איתה.

(3) מה מחפשים? את כל האיברים המקיימים לפחות תכונה אחת מכילים לפחות רצף אחד ולכן אנו מחפשים את $W(0)-E(0)$ .
(4) ישנה סימטריה בבעיה
(5) כעת נחשב את $W(r)$ עבור $1\leq r\leq 3$

W(1) \underset{\begin{matrix} \downarrow \\ \R{\text{סימטריה}} \end{matrix}}{=}\begin{pmatrix} 3 \\ 1 \end{pmatrix}|A_{1}|

$A_{1}$ היא כל הסידורים שמכילים את $111$ . לכן, נסדר את האיברים $111,2,2,2,3,3,3$ ולכן יש לנו $7$ איברים לסדר ונקבל כי הגודל של $A_{1}$ הינו $\frac{7!}{3!\cdot 3!}$ . לכן נקבל:

W(1)=\begin{pmatrix} 3 \\ 1 \end{pmatrix} \frac{7!}{3!\cdot 3!}

W(2)\underset{\begin{matrix} \downarrow \\ \R{\text{סימטריה}} \end{matrix}}{=} \begin{pmatrix} 3 \\ 2 \end{pmatrix}|A_{1}\cap A_{2}|

$A_{1}\cap A_{2}$ היא כל הסידורים שמכילים את $111$ ואת $222$ , לכן נסדר את האיברים $111,222,3,3,3$ . יש לנו $5$ איברים לסדר ונקבל כי הגודל של $A_{1}\cap A_{2}$ הינו $\frac{5!}{3!}$ ואז מתקיים:

W(2)=\begin{pmatrix} 3 \\ 2 \end{pmatrix} \frac{5!}{3!}

לבסוף נקבל:

W(3)=|A_{1}\cap A_{2}\cap A_{3}|=3!

שכן זוהי קביעת הסדר בין הרצפים $111,222,333$ .

לכן מתקבל:

E(0)=\sum_{r=0}^k (-1)^r W(r)=W(0)-W(1)+W(2)-W(3)

E(0)=\frac{9!}{3!\cdot3!\cdot 3!}-\begin{pmatrix} 3 \\ 1 \end{pmatrix} \frac{7!}{3!\cdot 3!}+\begin{pmatrix} 3 \\ 2 \end{pmatrix} \frac{5!}{3!}- 3!

וזוהי התשובה.

תרגיל

מהו מספר השלמים החיוביים בין $1$ ל- $300$ שאינם מתחלים ב- $2,5,11$ ?

אנו רוצים לחשב כמה מספרים יש לנו שלא מתחלקים ב- $2$ , לא מתחלקים ב- $11$ ולא מתחלקים ב- $5$ . (כל התנאים יחדיו)

(1) עולם: כמות המספרים בין $1$ ל- $300$ הינה $W(0)=300$ .
(2) תכונות:

מתחלק ב- $5$ .
לא מתחלק ב- $5$ .

מה מהם יותר קל? הם אותו דבר כי הם משלים. אך אנו משווים בין חיתוכים - יותר קל פה הוא מתחלקים.
טריק: נגדיר $c_{1}=2,c_{2}=5,c_{3}=11$ ואז אפשר להגדיר את התכונות יפה כך:
$A_{i}$ מתחלק ב- $c_{i}$ כאשר $1\leq i\leq 3$ .

(3) מה מחפשים? אם אף אחת מהתכונות לא קיימת את המספר לא מתחלק ב- $2,5,11$ שזה בדיוק מה שאנו מחפשים ולכן זה $E(0)$ .
(4) האם יש סימטריה? לא שכן אין שום קשר בין המספרים שמתחלקים ב- $2$ למספרים המתחלקים ב- $11$ או ב- $5$ .
(5) נחשב:

הערה

עבור $p_{1},p_{2},\dots,p_{t}$ ראשוניים, אזי כמות המספרים בין $1$ ל- $s$ המתחלקים ב- $p_{1},\dots,p_{t}$ היא:

\left\lfloor \frac{s}{p_{1}p_{2}\cdots p_{t}} \right\rfloor

לכן מתקיים:

W(1)=|A_{1}|+|A_{2}|+|A_{3}|

|A_{1}|= \left\lfloor \frac{300}{2} \right\rfloor

|A_{2}|=\left\lfloor \frac{300}{5} \right\rfloor

|A_{3}|=\left\lfloor \frac{300}{11} \right\rfloor

W(2)=|A_{1}\cap A_{2}|+|A_{1}\cap A_{3}|+|A_{2}\cap A_{3}|=\left\lfloor \frac{300}{2\cdot 5} \right\rfloor +\left\lfloor \frac{300}{5\cdot 11} \right\rfloor +\left\lfloor \frac{300}{2\cdot 11} \right\rfloor

W(3)=|A_{1}\cap A_{2}\cap A_{3}|=\left\lfloor \frac{300}{5\cdot 2\cdot 11} \right\rfloor

תרגיל

נתונים $n$ זוגות של גבר ואישה. $k$ מתוכם רוצים להתגרש.
בכמה דרכים ניתן לסדר את הגברים בשורה ואת הנשים בשורה מולם כך שאף זוג שמעוניין להתגרש לא יהיה אחד מול השני.

(1) עולם:

יש $n!$ אפשרויות לסדר גברים בשורה
יש $n!$ אפשרויות לסדר נשים בשורה

לכן, סה"כ $(n!)^2$ אפשרויות.

(2) תכונות:

הזוג ה- $i$ אחד מול השני
הזוג ה- $i$ לא אחד מול השני

קל יותר לבחור את אופציה $1$ עבור $1\leq i \leq k$ . כלומר, נגדיר $A_{i}$ כאפשרויות שבהן הזוג $i$ אחד מול השני.

(3): מה מחפשים? אם אף אחת מהתכונות לא מתקיימת, אף זוג גרוש לא עומד אחד מול השני ולכן, אנו צריכים להשיג את $E(0)$ .

(4) האם יש סימטריה? יש סימטריה

(5) חישוב $W(r)$ עבור $1\leq r\leq k$ .
נחשב את $|A_{1}|$ . נקבע את מיקומם של $n$ הגברים וזה יהיה $n!$ . כעת, נקבע את מיקום הנשים. המיקום של האישה ה- $1$ נקבע מראש ולכן יש $(n-1)!$ אפשרויות. לכן $|A_{1}|=n!(n-1)!$ .

W(1) \underset{\begin{matrix} \downarrow \\ \R{\text{סימטריה}} \end{matrix}}{=}\begin{pmatrix} k \\ 1 \end{pmatrix}|A_{1}|=\begin{pmatrix} k \\ 1 \end{pmatrix}n!(n-1)!

נדרש למצוא ביטוי כללי עבור $W(r)$ ל- $1\leq r\leq k$ כלשהו:

W(r) \underset{\begin{matrix} \downarrow \\ \R{\text{סימטריה}} \end{matrix}}{=}\begin{pmatrix} k \\ r \end{pmatrix}|A_{1}\cap A_{2} \cap \dots \cap A_{r}|

עבור כל קבוצה מתקיים כי צריך לסדר אישה אחת פחות ולכן $|A_{1}\cap A_{2}\cap \dots \cap A_{r}|=n!(n-r)!$ . אזי:

W(r)=\begin{pmatrix} k \\ r \end{pmatrix}n!(n-r)!

כעת נמצא את התשובה הסופית:

E(0)=\sum_{r=0}^k (-1)^rW(r)=\sum_{r=0}^k (-1)^r \begin{pmatrix} k \\ r \end{pmatrix}n!(n-r)!

הערה

עבור $n=k$ נקבל:

E(0)=\sum_{r=0}^n (-1)^r \begin{pmatrix} n \\ r \end{pmatrix} n!(n-r)!=n!\sum_{r=0}^n (-1)^r \begin{pmatrix} n \\ r \end{pmatrix}(n-r)!

מאיפה הביטוי הזה מוכר לנו? $D(n)$ הוא מספר האפשרויות לסדר $n$ אנשים ככה ש- $i$ לא במקום ה- $i$ ולכן מתקיים:

E(0)=n!D(n)

תרגיל

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

\sum_{i=0}^n (-1)^i \begin{pmatrix} n \\ i \end{pmatrix}(n-i)^n=n!

הערה (ענן המחשבות)

בצד שמאל אנו רואים שיש לנו יצור של סוג של הכלה-הפרדה אשר מתאר את $E(0)$ כאשר:

W(r)=\begin{pmatrix} n \\ r \end{pmatrix}(n-r)^n

כאשר יש לנו $n$ תכונות ויש סימטריה שכן יש לנו $\begin{pmatrix}n\\ r\end{pmatrix}$ .
פה אנחנו מקווים שזה סימטריה וזה גודל חיתוך, כלומר: $|A_{1}\cap A_{2}\cap\dots \cap A_{r}|=(n-r)^n$ .
גודל העולם הינו $W(0)=n^n$ .
העולם שלנו יכול להיות לוקטור באורך $n$ מעל $\left\{ 1,\dots,n \right\}$ . נשים לב כי כאשר אנחנו חותכים $r$ תכונות, אנו נפגעים בא"ב שכן הבחזקת $n$ היא האורך.
נציע את הדבר הבא: $A_{i}$ היא קבוצת כל הוקטורים כאשר האות $i$ לא מופיעה.
האם יש סימטריה? כן. האם זה מתאים לבעיה? כן.
איזו בעיה הדבר הזה פותר? כל הוקטורים באורך $n$ מעל $\left\{ 1,\dots,n \right\}$ אשר לא מקיימים אף תכונה. כלומר, כל הוקטורים באורך $n$ שבהם כל אות מופיעה לפחות פעם אחת(שזה היה בדיוק פעם אחת)

הוכחה:
בעיה: מהו מספר הוקטורים מעל $\left\{ 1,\dots,n \right\}$ באורך $n$ אשר בהם מופיעה כל אות לפחות פעם אחת.
צד ימין: אורך הוקטור הוא $n$ ויש $n$ אפשרויות לאותיות. תחילה, נמקם את כל האותיות שאנו חייבים לשים(כלומר, פעם אחת כל אות) לאות הראשונה יש לנו $n$ אפשרויות, לאות השניה יש לנו $n-1$ אפשרויות וכך הלאה עד שאנו מציבים את כל האותיות. מכיוון שיש לנו $n$ מקומות להציב ו- $n$ אותיות אזי כאשר אנו מסיימים להציב כל אות פעם אחת אנו מגיעים לסוף המילה. לכן, יש בדיוק $n\cdot (n-1)\cdots2\cdot 1=n!$ אפשרויות.
צד שמאל: [ראו טיוטה למעלה ואם יהיה לי זמן אני אכתוב את זה פורמלית כי הוא פשוט דילג על פירמול של שניהם וניסיתי להספיק כמה שיותר]
∎

תרגיל

נתונות שתי קוביות זהות. מטילים אותן $n$ פעמים ובכל סדרה של $n$ הטלות סופרים כמה דאבלים שונים יצאו.
הדאבלים הם $\left\{ \left\{ 1,1 \right\},\left\{ 2,2 \right\},\left\{ 3,3 \right\},\left\{ 4,4 \right\},\left\{ 5,5 \right\},\left\{ 6,6 \right\} \right\}$ .
סדרת הטלות תקרא מוצלחת אם ייצאו בה כל אחד מששת הדאבלים השונים לפחות פעם אחת.
כמה סדרות מוצלחות ישנן, כאשר סדר ההטלות בסדרה חשוב?

נבצע זאת באמצעות הכלה-הפרדה.
(1) עולם: תוצאה של זוג קוביות ⇐ יש $\mathbb{C}_{6}^2$ אפשרויות לכל הטלת קוביות ולכן יש $W(0)=(\mathbb{C}_{6}^2)^n$ אפשרויות סה"כ.
(2) תכונות:

מכיל $\left\{ i,i \right\}$
לא מכיל $\left\{ i,i \right\}$

יהיה לנו יותר קל להתעסק עם לא מכיל ולכן נבחר בו. כלומר, $A_{i}$ היא קבוצת כל ההטלות שבהן הזוג $\left\{ i,i \right\}$ לא מופיע.
(3) האופציה שאנו מחפשים היא שכל התכונות לא ייתקמו, ובכך כל זוג יופיע לפחות פעם אחת. זה $E(0)$ .
(4) ישנה סימטריה בבעיה
(5) חישוב $W(r)$ עבור $1\leq r\leq 6$ :

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

עבור $r$ כללי יש $r$ דאבלים אסורים ולכן נקבל:

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

הכלה והפרדה

E(0)=\sum_{r=0}^{\R{\text{כמות התכונות}}} (-1)^r W(r)

כאשר $W(r)=\begin{matrix}\R{\text{סכום כל החיתוכים}}\\ \R{\text{של r תכונות}}\end{matrix}$ .
כלומר, עבור $A_{1},A_{2},A_{3}$ מתקיים:

W(1)=|A_{1}|+|A_{2}|+|A_{3}|

W(2)=|A_{1}\cap A_{2}|+|A_{1} \cap A_{3}|+|A_{2} \cap A_{3}|

W(3)=|A_{1}\cap A_{2}\cap A_{3}|

תבנית פתרון עם הכלה-הפרדה

עולם
תכונות
מה מחפשים? $E(0)/W(0)-E(0)$
סימטריה(חיתוך של כל $t$ תכונות זהה.) - כן או לא? (הדבר היחיד שלא צריך לנמק בקורס)
חישוב $W(r)$
הצבה

תרגול

תרגיל

כמה פתרונות קיימים למשוואה: $x_{1}+x_{2}+x_{3}+x_{4}+x_{5}+x_{6}=20$ כך שלכל $i$ מתקיים $0\leq x_{i}\leq 8$ ?

(3) מה מחפשים? $E(0)$ . כלומר, כל פתרונות שלא מקיימים אף תכונה. כלומר, לכל $i$ לא מתקיים $x_{i}>8$ ולכן $0\leq x_{i}\leq 8$ .

(4) סימטריה: יש סימטריה!

(5) חישוב $W$ -ים עבןר $0\leq r\leq 6$ .

W(1)=|A_{1}|+|A_{2}|+|A_{3}|+|A_{4}|+\dots+|A_{6}|

W(1)=\begin{pmatrix} 6 \\ 1 \end{pmatrix}|A_{1}|=\begin{pmatrix} 6 \\ 1 \end{pmatrix}\mathbb{C}_{6}^{11}

כעת נמשיך:

W(2)\underset{\begin{matrix} \downarrow \\ \R{\text{סימטריה}} \end{matrix}}{=}\begin{pmatrix} 6 \\ 2 \end{pmatrix}|A_{1}\cap A_{2}|

|A_{1}\cap A_{2}|=\mathbb{C}_{6}^{20-9-9}=\mathbb{C}_{6}^{2}

לכן:

W(2)=\begin{pmatrix} 6 \\ 2 \end{pmatrix}\mathbb{C}_{6}^2

E(0)=\sum_{r=0}^{6} (-1)^{r}W(r)=W(0)-W(1)+W(2)=\mathbb{C}_{6}^{20}-\begin{pmatrix} 6 \\ 1 \end{pmatrix}\mathbb{C}_{6}^{11}+\begin{pmatrix} 6 \\ 2 \end{pmatrix}\mathbb{C}_{6}^2

וזוהי התשובה.

תרגיל

בכמה דרכים ניתן לסדר את המספרים $1,1,1,2,2,2,3,3,3$ כך שיווצר לפחות רצף אחד של $3$ מספרים זהים?

$A_{i}$ - קיים הרצף $iii$
$A_{i}$ - לא קיים הרצף $iii$

אנחנו נבחר את האופציה הראשונה שכן קל יותר לעבוד איתה.

W(1) \underset{\begin{matrix} \downarrow \\ \R{\text{סימטריה}} \end{matrix}}{=}\begin{pmatrix} 3 \\ 1 \end{pmatrix}|A_{1}|

W(1)=\begin{pmatrix} 3 \\ 1 \end{pmatrix} \frac{7!}{3!\cdot 3!}

W(2)\underset{\begin{matrix} \downarrow \\ \R{\text{סימטריה}} \end{matrix}}{=} \begin{pmatrix} 3 \\ 2 \end{pmatrix}|A_{1}\cap A_{2}|

W(2)=\begin{pmatrix} 3 \\ 2 \end{pmatrix} \frac{5!}{3!}

לבסוף נקבל:

W(3)=|A_{1}\cap A_{2}\cap A_{3}|=3!

שכן זוהי קביעת הסדר בין הרצפים $111,222,333$ .

לכן מתקבל:

E(0)=\sum_{r=0}^k (-1)^r W(r)=W(0)-W(1)+W(2)-W(3)

E(0)=\frac{9!}{3!\cdot3!\cdot 3!}-\begin{pmatrix} 3 \\ 1 \end{pmatrix} \frac{7!}{3!\cdot 3!}+\begin{pmatrix} 3 \\ 2 \end{pmatrix} \frac{5!}{3!}- 3!

וזוהי התשובה.

תרגיל

מהו מספר השלמים החיוביים בין $1$ ל- $300$ שאינם מתחלים ב- $2,5,11$ ?

אנו רוצים לחשב כמה מספרים יש לנו שלא מתחלקים ב- $2$ , לא מתחלקים ב- $11$ ולא מתחלקים ב- $5$ . (כל התנאים יחדיו)

(1) עולם: כמות המספרים בין $1$ ל- $300$ הינה $W(0)=300$ .
(2) תכונות:

מתחלק ב- $5$ .
לא מתחלק ב- $5$ .

הערה

עבור $p_{1},p_{2},\dots,p_{t}$ ראשוניים, אזי כמות המספרים בין $1$ ל- $s$ המתחלקים ב- $p_{1},\dots,p_{t}$ היא:

\left\lfloor \frac{s}{p_{1}p_{2}\cdots p_{t}} \right\rfloor

לכן מתקיים:

W(1)=|A_{1}|+|A_{2}|+|A_{3}|

|A_{1}|= \left\lfloor \frac{300}{2} \right\rfloor

|A_{2}|=\left\lfloor \frac{300}{5} \right\rfloor

|A_{3}|=\left\lfloor \frac{300}{11} \right\rfloor

W(2)=|A_{1}\cap A_{2}|+|A_{1}\cap A_{3}|+|A_{2}\cap A_{3}|=\left\lfloor \frac{300}{2\cdot 5} \right\rfloor +\left\lfloor \frac{300}{5\cdot 11} \right\rfloor +\left\lfloor \frac{300}{2\cdot 11} \right\rfloor

W(3)=|A_{1}\cap A_{2}\cap A_{3}|=\left\lfloor \frac{300}{5\cdot 2\cdot 11} \right\rfloor

תרגיל

(1) עולם:

יש $n!$ אפשרויות לסדר גברים בשורה
יש $n!$ אפשרויות לסדר נשים בשורה

לכן, סה"כ $(n!)^2$ אפשרויות.

(2) תכונות:

הזוג ה- $i$ אחד מול השני
הזוג ה- $i$ לא אחד מול השני

קל יותר לבחור את אופציה $1$ עבור $1\leq i \leq k$ . כלומר, נגדיר $A_{i}$ כאפשרויות שבהן הזוג $i$ אחד מול השני.

(3): מה מחפשים? אם אף אחת מהתכונות לא מתקיימת, אף זוג גרוש לא עומד אחד מול השני ולכן, אנו צריכים להשיג את $E(0)$ .

(4) האם יש סימטריה? יש סימטריה

W(1) \underset{\begin{matrix} \downarrow \\ \R{\text{סימטריה}} \end{matrix}}{=}\begin{pmatrix} k \\ 1 \end{pmatrix}|A_{1}|=\begin{pmatrix} k \\ 1 \end{pmatrix}n!(n-1)!

נדרש למצוא ביטוי כללי עבור $W(r)$ ל- $1\leq r\leq k$ כלשהו:

W(r) \underset{\begin{matrix} \downarrow \\ \R{\text{סימטריה}} \end{matrix}}{=}\begin{pmatrix} k \\ r \end{pmatrix}|A_{1}\cap A_{2} \cap \dots \cap A_{r}|

עבור כל קבוצה מתקיים כי צריך לסדר אישה אחת פחות ולכן $|A_{1}\cap A_{2}\cap \dots \cap A_{r}|=n!(n-r)!$ . אזי:

W(r)=\begin{pmatrix} k \\ r \end{pmatrix}n!(n-r)!

כעת נמצא את התשובה הסופית:

E(0)=\sum_{r=0}^k (-1)^rW(r)=\sum_{r=0}^k (-1)^r \begin{pmatrix} k \\ r \end{pmatrix}n!(n-r)!

הערה

עבור $n=k$ נקבל:

E(0)=\sum_{r=0}^n (-1)^r \begin{pmatrix} n \\ r \end{pmatrix} n!(n-r)!=n!\sum_{r=0}^n (-1)^r \begin{pmatrix} n \\ r \end{pmatrix}(n-r)!

מאיפה הביטוי הזה מוכר לנו? $D(n)$ הוא מספר האפשרויות לסדר $n$ אנשים ככה ש- $i$ לא במקום ה- $i$ ולכן מתקיים:

E(0)=n!D(n)

תרגיל

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

\sum_{i=0}^n (-1)^i \begin{pmatrix} n \\ i \end{pmatrix}(n-i)^n=n!

הערה (ענן המחשבות)

בצד שמאל אנו רואים שיש לנו יצור של סוג של הכלה-הפרדה אשר מתאר את $E(0)$ כאשר:

W(r)=\begin{pmatrix} n \\ r \end{pmatrix}(n-r)^n

תרגיל

מכיל $\left\{ i,i \right\}$
לא מכיל $\left\{ i,i \right\}$

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

עבור $r$ כללי יש $r$ דאבלים אסורים ולכן נקבל:

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