ראו: האתר של שרי בחלק של קומבינטוריקה.

1 - עקרונות הספירה

קומבינטוריקה: תחום מתמטי שעוסק בחישוב עוצמתן של קבוצות סופיות.

1.1 - עקרונות הספירה הבסיסיים

נתחיל מכמה עקרונות בסיסיים:

הגדרה 1 (עקרון החיבור)

אם $A,B$ קבוצות זרות, אז:

|A \cup B|=|A|+|B|

דוגמה

נניח יש לנו בית קפה ואנו רוצים להזמין משקה חם - נרצה להזמין קפה או תה.
בדוגמה שלנו, עוצמת קבוצת סוגי הקפה(נסמנה $C$ ) היא 7 ועוצמת קבוצת סוגי התה(נסמנה $T$ ) היא 5.

כמה אפשרויות בחירה יש לנו סה"כ?
מכיוון שאין קפה שהוא גם תה, נוכל להשתמש בעקרון החיבור:

|C \cup T|=|C|+|T|=7+5=12

בהמשך אנו נדבר על מה קורה אם יש איברים זהים בשתי הקבוצות(רמז עצמי, משפט המימדים)

הגדרה 2 (עקרון הכפל)

|A \times B|=|A|\cdot |B|

תזכורת קטנה: $A\times B$ היא מכפלה קרטזית בין $A$ ל- $B$ .

דוגמה

|\left\{ 1,2,3 \right\}\times \left\{ a,b \right\}|=|\left\{ (1,a),(2,a),(3,a),(1,b),(2,b),(3,b) \right\}|=6

|\left\{ 1,2,3 \right\}\times \left\{ a,b \right\}|=|\left\{ 1,2,3 \right\}|\cdot |\left\{ a,b \right\}|=3\cdot 2 = 6

דוגמה

בדוגמה שלנו ממקודם, נרצה לבחור כעת זוג של תה וקינוח. כלומר, אנו רוצים בעצם לבחור משקה אחד מ- $T$ וקינוח מהקבוצה $D$ (קבוצת הקינוחים).

|T\times D|=5\cdot 8 = 40

נשים לב כי זהו בדיוק עקרון הכפל.

הגדרה 3 (כללת עקרון הכפל)

עבור $k \in \mathbb{N}$ מתקיים:

|A_{1}\times A_{2}\times\dots \times A_{k}|=|A_{1}|\cdot |A_{2}|\dots |A_{k}|

משפט

יהי $R \subseteq A\times B$ . אם לכל $a \in A$ קיימים $k$ איברים מ- $B$ איתו ב- $R$ אז: $|R|=|A|\cdot k$
ובאופן סימטרי, אם לכל $b \in B$ קיימים $k$ איברים מ- $A$ איתו ב- $R$ אז: $|R|=k\cdot |B|$ .

דוגמה

כמה מספרים זוגיים ישנם בין $0$ ל- $99$ ? מחציתם ולכן $50$ .
הסתכלות נוספת: מספר דו ספרתי הוא זוג סדור: $(\R{\text{ספרת עשרות}},\R{\text{ספרת אחדות}})$ ולכן, קבוצת המספרים בין $0$ ל- $99$ היא $\left\{ 0,1,\dots,9 \right\}\times \left\{ 0,1,\dots,9 \right\}$ מתוכם, המספרים הזוגיים הם כאלו שספרת האחדות שלהן זוגית. יש בדיוק 5 ספרות זוגיות.( $0,2,4,6,8$ )
לכן, הם יחס $R \subseteq \left\{ 0,\dots,9 \right\}\times \left\{ 0,\dots,9 \right\}$ המקיים כי לכל ספרת עשרות יש 5 איברים מתוך ספרות האחדות שאיתה ביחס ולכן, נוכל להשתמש במשפט הנ"ל:

|R|=|\left\{ 0,1,\dots,9 \right\}|\cdot 5 = 50

לכמה מספרים זוגיים כאלו יש 2 ספרות שונות?
קבוצת הזוגיים היא למעשה $\left\{ 0,1,\dots,9 \right\}\times \left\{ 0,2,4,6,8 \right\}$ (אם היינו מסתכלים על זה ככה, היינו מגיעים לאותו הדבר בחלק הקודם)
נגדיר עוד פעם יחס שהוא תת קבוצה של המכפלה הקרטזית הזו: $R \subseteq \left\{ 0,\dots,9 \right\}\times \left\{ 0,2,4,6,8 \right\}$ . לכל ספרה מבין הזוגיות, כל האיברים נמצאים איתה ביחס מלבד היא עצמה. לכן נוכל להביע זאת בקלות באמצעות המשפט הנ"ל.
בעצם, לכל ספרת אחדות $i$ ישנן $9$ ספרות עשרות איתה ב- $R$ (כולן פרט ל- $i$ ) ולכן:

|R|=9\cdot 5 = 45

תהי $A$ קבוצה בגודל $n$ . אנו נשאל בכמה דרכים שונות ניתן לבחור $k$ איברים מתוך $A$ ?
נדרש לחדד את השאלה:

האם מותרות חזרות?
האם סדר משנה? (האם לבחור את 2 ואז את 3 שונה מלבחור את 3 ואז את 2)

אנו ננתח את כל אחת מהאפשרויות האלו ונספור כמה אפשרויות יש לנו בכל מצב.

מותרות חזרות והסדר משנה:
נוכל לבחור לאיבר הראשון $n$ אפשרויות
" " " " השני $n$ אפשרויות
וכך הלאה. נשים לב כי זהו עקרון הכפל, כי אנו יכולים לבחור $n$ אפשרויות לכל אחד מה- $k$ איברים. במילים אחרות, $n^k$ . זה שקול לחישוב העוצמה: $|\underbrace{A\times A\times\dots \times A}_{k}|$ .

דוגמה

נוכל לחשוב על טופס טוטו שבו מהמרים על משחקי כדורגל. יש 3 עמודות: קבוצה מארחת, קבוצה אורחת ותיקו.
בכל טופס טוטו יש 16 משחקים. בכל משחק יש 3 אפשרויות. כמובן שהסדר משנה ויכולות להיות חזרות במצב זה. זה מתאים למה שראינו.

A=\left\{ 1,2,X \right\}

כאשר 1 זו קבוצת הבית, 2 זו הקבוצה האורחת ו- $X$ זה תיקו.
⇐ יש $3^{16}$ אפשרויות למילוי טופס לוטו. לכן יש סיכוי של 1 ל- $43,046,721$ למלא טופס טוטו נכון לחלוטין.

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

הערה

n\cdot (n-1) \cdot (n-2) \dots (n-k+1){\color{red}\underbrace{\cdot\; \dots\; \cdot 1}_{(n-k)!}}=\frac{n!}{\color{red}(n-k)!}

בחירה בלי חזרות כשהסדר לא משתנה: זה כבר קצת יותר מסובך לחישוב וננסה כעת למצוא דרך להביע זאת בקלות.
$\frac{n!}{k!(n-k)!}$

הערה

לביטוי הזה קוראים מקדם הבינום ונדבר עליו בהמשך.

דוגמה

נרצה לבחור 2 איברים מתוך 3 איברים. נסתכל על כל הסידורים האפשריים של שלושת האיברים:

\begin{matrix} 1 & 2 & 3 \\ 1 & 3 & 2 \\ 2 & 1 & 3 \\ 2 & 3 & 1 \\ 3 & 1 & 2 \\ 3 & 2 & 1 \end{matrix}

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

\frac{3!}{2!\cdot 1!}

הגדרה (סימון למקדם הבינום)

למקדם הבינום, שנקרא גם פונקצית $choose$ יש סימון והוא:

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

לפעמים נקרא גם $n$ מעל $k$ או $k$ מתוך $n$ .

דוגמה

כעת, נביט בטופס לוטו (שרי כנראה מומחית בהימורים או משהו). כל טופס בנוי מאוסף של טבלאות ואנו נסתכל על אחת מהן.
בכל טבלה יש 37 מספרים ואנו צריכים לבחור 6 מספרים. הסדר לא משנה ואסור חזרות (אין דרך לסמן את 2 פעמיים)
כמה אפשרויות יש לנו למילוי טבלה אחת?

\begin{pmatrix} 37 \\ 6 \end{pmatrix}=\frac{37!}{6!\cdot 31!}\underset{\begin{matrix} \downarrow \\ \R{\text{שרי חישבה במחשבון}} \end{matrix}}{=}2,324,784

הערה: יש יותר סיכוי להיפגע בתאונת דרכים מאשר לזכות בטופס לוטו.

בחירה עם חזרות כשהסדר לא משנה: יש לנו $n$ איברים בקבוצה ואנו רוצים לדעת לגבי כל איבר כמה פעמים בחרנו בו. זה מקרה מדוייק לכך שהסדר לא משנה - לא איכפת לי מתי בחרתי, רק כמות הפעמים שבחרתי.
נוכל לחשוב על זה בסלים - בכל סל נשים כדורים כמספר הפעמים שבחרנו באיבר.

בחירה של איבר $i$ שקולה לכדור בתוך סל $i$ . סה"כ יש לנו $k$ כדורים.
"קידוד" בינארי של בחירה(כאשר $0$ אומר שיש כדור ו-1 מבטא מעבר בין סלים): $00110$ (2 כדורים בסל הראשון, 0 בסל השני ו-1 בסל השלישי)
מתקבלת סדרה בינארית עם $k$ אפסים ו- $n-1$ אחדים. ולהפך: כל סדרה בינארית כאזת שקולה לפיזור כדורים בין הסלים.
⇐ עוצמת קבוצת הסדרות = מספר האפשרויות הדרוש.
כמה סדרות כאלו קיימות? כל סדרה היא באורך $k+n-1$ וצריך לבחור את המיקומים בסדרה שבהם מופיע $0$ : יהיו לנו $k$ מיקומים שונים. זוהי בחירה ללא חזרות כשהסדר לא משנה. נשים לב שכבר ראינו את דבר זה ואנו יודעים לפתור זאת: ${\color{purple}\begin{pmatrix}n-1+k\\n-1\end{pmatrix}=}\begin{pmatrix}n-1+k \\ k\end{pmatrix}$ .
זה לא משנה אם אנחנו בוחרים את $k$ האפסים או את $n-1$ האחדים כי המכנה נשאר זהה וכך גם המונה.

משפט (סיכום הקטע)

עבור בחירה של $k$ איברים מתוך $n$ :

עם חזרות והסדר משנה: $n^k$
בלי חזרות כשהסדר משנה: $\frac{n!}{(n-k)!}$
בלי חזרות כשהסדר לא משנה: $\begin{pmatrix}n\\ k\end{pmatrix}=\frac{n!}{k!(n-k)!}$
עם חזרות כשהסדר לא משנה: $\begin{pmatrix}n-1+k\\ k\end{pmatrix}=\frac{(n-1+k)!}{k!(n-1)!}$

1.2 - הבינום של ניוטון

הבינום של ניוטון הוא ביטוי מהצורה $(x+y)^n=\underbracket{(x+y)(x+y)\dots(x+y)}_{n}$ ואנו נרצה למצוא ביטוי לפתיחת הסוגריים.
לדוגמה: $(x+y)^2=(x+y)(x+y)=x^2+2xy+y^2$ . מה יש לנו פעמיים $xy$ ? כי יש לנו 2 אפשרויות לבחור $x$ ו- $y$ ביחד - מהכופל הראשון והשני ומהכופל השני וראשון.
באופן כללי כדי לפתוח סוגריים: עוברים על כל כופל $(x+y)$ ובוחרים ממנו $x$ או $y$ . כל נוצר מחובר בסכום הכולל. בבחירה שכזו, אם בוחרים ב- $k$ מהכופלים את $x$ , אז מכל $n-k$ הנותרים בוחרים את $y$ . המחובר שמתקבל: $x^ky^{n-k}$ .
כמה פעמים מחובר זה יופיע בסכום? $\begin{pmatrix}n \\ k\end{pmatrix}$ כלומר, ב- $k$ מהכופלים בוחרים את $x$ ולכן יש לנו $k$ מתוך $n$ פעמים שהמחובר הנ"ל יופיע במכפלה הכללית.
אפשר לבחור בין $0$ פעמים $x$ ל- $n$ פעמים $x$ ולכן הסכום שנקבל כשנפתח את הסוגריים הינו:

(x+y)^n=\sum_{k=0}^n \begin{pmatrix} n \\ k \end{pmatrix} x^ky^{n-k}

משפט (הבינום של ניוטון)

עבור כל $n \in \mathbb{N}$ מתקיים:

(x+y)^n=\sum_{k=0}^n \begin{pmatrix} n \\ k \end{pmatrix}x^ky^{n-k}

כעת, נכליל את הרעיון לפתיחת סוגריים של מולטינום.

הגדרה 4 (מולטינום)

מולטינום הוא יצור מהצורה: $(x_{1}+\dots+x_{m})^n$ .

כאשר נפתח את הסוגריים נקבל $(x_{1}+\dots+x_{m})(x_{1}+\dots+x_{m})\dots(x_{1}+\dots+x_{m})$ . מתקבל סכום של איברים מהצורה הבאה:

x_{1}^{i_{1}}x_{2}^{i_{2}}\dots x_{m}^{i_{m}}

כך ש: $\sum_{j=1}^n i_{j}=n$ .

דוגמה

אם נקח את $(x_{1}+x_{2}+x_{3})$ ונעלה אותו בחזקה $4$ - בין היתר יהיו לנו מחוברים מהצורה הבאה:

x_{1}^1\cdot x_{2}^1\cdot x_{3}^2

אם נרחיב את זה, ב- $(x_{1}+x_{2}+x_{3})^n$ אז יהיו מחוברים מהצורה הבאה:

x_{1}^{i_{1}}x_{2}^{i_{2}}x_{3}^{i_{3}}

כך ש- $i_{1}+i_{2}+i_{3}=n$ .
כמה פעמים יופיע כל מחובר שכזה בסכום? כלומר, בכמה דרכים שונות אנו יכולים לבחור $i_{1}$ פעמים את $x_{1}$ , ו- $i_{2}$ פעמים את $x_{2}$ ו- $i_{3}$ פעמים את $x_{3}$ .
יש לנו $\begin{pmatrix}n\\i_{1}\end{pmatrix}$ אפשרויות לבחירת $x_{1}$ מבין $n$ הכופלים. מבין מה שנותר נדרש כעת לבחור את $x_{2}$ . כלומר, יש $\begin{pmatrix}n-i_{1}\\i_{2}\end{pmatrix}$ אפשרויות לבחירת $x_{2}$ מבין $n-i_{1}$ הכופלים שנותרו וכך גם יש לנו $\begin{pmatrix}n-i_{1}-i_{2}\\i_{3}\end{pmatrix}$ אפשרויות לבחור את $x_{3}$ מבין $n-i_{1}-i_{2}$ הכופלים שנותרו.
נשים לב כי בדוגמה יש לנו את עקרון הכפל ולפיו:

\begin{pmatrix} n \\ i_{1} \end{pmatrix}\begin{pmatrix} n-i_{1} \\ i_{2} \end{pmatrix}\begin{pmatrix} n-i_{1}-i_{2} \\ i_{3} \end{pmatrix}=\frac{n!}{\cancel{ (n-i_{1})! }(i_{1})!} \frac{\cancel{ (n-i_{1})! }}{\cancel{ (n-i_{1}-i_{2})! }(i_{2})!} \frac{\cancel{ (n-i_{1}-i_{2})! }}{(n-i_{1}-i_{2}-i_{3})!(i_{3})!}

נשים לב כי $(n-i_{1}-i_{2}-i_{3})=0$ ולכן:

= \frac{n!}{i_{1}!\cdot i_{2}!\cdot i_{3}!}

וזה מספר הפעמים שיופיע הגורם הנ"ל בסכום.

נסיק מהדוגמה כי אופן כללי המחובר $x_{1}^{i_{1}}\dots x_{m}^{i_{m}}$ מופיע:

\frac{n!}{\prod_{1\leq j\leq m}(i_{j})!}

נסמן: $\begin{pmatrix}n\\i_{1},i_{2},\dots,i_{m}\end{pmatrix}$ . סימון זה הוא הכללה של $\begin{pmatrix}n\\ k\end{pmatrix}$ .

משפט (הכללת הבינום של ניוטון)

עבור $m,n \in \mathbb{N}$ מתקיים:

(x_{1}+\dots+x_{m})^n=\sum_{\begin{matrix} 0\leq i_{1},i_{2},\dots,i_{m}\leq n \\ \\ \sum_{j}i_{j}=n \R{\text{כך ש }} \end{matrix}} \begin{pmatrix} n \\ i_{1},\dots,i_{m} \end{pmatrix} x_{1}^{i_{1}}x_{2}^{i_{2}}\dots x_{m}^{i_{m}}

כאשר $\begin{pmatrix}n\\ i_{1},i_{2},\dots,i_{m}\end{pmatrix}=\frac{n!}{\prod_{1\leq j\leq m}(i_{j})!}$ .

דוגמה

(x_{1}+x_{2}+x_{3})^2=\overbrace{\begin{pmatrix} 2 \\ 2,0,0 \end{pmatrix}}^{1}\cdot x_{1}^2+\overbrace{\begin{pmatrix} 2 \\ 0,2,0 \end{pmatrix}}^1\cdot x_{2}^2+\overbrace{\begin{pmatrix} 2 \\ 0,0,2 \end{pmatrix}}^1 \cdot x_{3}^2+

\underbrace{\begin{pmatrix} 2 \\ 1,1,0 \end{pmatrix}}_{2}\cdot x_{1}x_{2}+\underbrace{\begin{pmatrix} 2 \\ 0,1,1 \end{pmatrix}}_{2}\cdot x_{2}x_{3}+\underbrace{\begin{pmatrix} 2 \\ 1,0,1 \end{pmatrix}}_{2}\cdot x_{1}x_{3}

1.3 - זהויות קומבינטוריות

טענה (1)

\sum_{k=0}^n \begin{pmatrix} n \\ k \end{pmatrix}=2^n

הוכחה אלגברית:

2^n=(1+1)^n \underset{\begin{matrix} \downarrow \\ \R{\text{נציב בבינום}} \end{matrix}}{=} \sum_{k=0}^n \begin{pmatrix} n \\ k \end{pmatrix} 1^k \cdot 1^{n-k}=\sum_{k=0}^n \begin{pmatrix} n \\ k \end{pmatrix}

∎

הוכחה קומבינטורית:
מצד שמאל: עוברים על כל גדלי תת הקבוצות האפשריים של קבוצה בגודל $n$ מ- $0$ ועד $n$ ולכל גודל $k$ סופרים כמה תת קבוצות יש בגודל $k$ . כך מקבלים את מספר התת קבוצות של קבוצה בגודל $n$ .
מצד ימין: לכל איבר בקבוצה בגודל $n$ ישנן 2 אפשרויות: להשתייך לתת-קבוצה או לא להשתייך.
⇐ 2 אפשרויות לאיבר הראשון, 2 אפשרויות לשני וכך הלאה עד לאיבר ה- $n$ .
⇐ מכיוון שאנו צריכים להחליט לגבי כל אחד מהאיברים, נפעיל את עקרון הכפל ולכן מקבלים $2\cdot2\dots2=2^n$
⇐ שני הצדדים סופרים את מספר תת הקבוצות של קבוצה בגודל $n$ .
∎

הערה

ניתן להוכיח גם באינדוקציה

טענה (2)

\sum_{k=1}^n k\cdot \begin{pmatrix} k \\ n \end{pmatrix}=n\cdot 2^{n-1}

הוכחה אלגברית:

k\cdot \begin{pmatrix} n \\ k \end{pmatrix}=k \cdot \frac{n!}{k!(n-k)!}=\frac{n!}{(k-1)!(n-k)!}=n \frac{(n-1)!}{(k-1)!(n-k)!}=n \cdot \begin{pmatrix} n-1 \\ k-1 \end{pmatrix}

מכאן:

\sum_{k=1}^n k \begin{pmatrix} n \\ k \end{pmatrix}=\sum_{k=1}^n n \begin{pmatrix} n-1 \\ k-1 \end{pmatrix}=n\sum_{k=1}^n \begin{pmatrix} n-1 \\ k-1 \end{pmatrix}=n\sum_{k=0}^{n-1} \begin{pmatrix} n-1 \\ k \end{pmatrix}\underset{\begin{matrix} \downarrow \\ \R{\text{לפי הטענה הראשונה}} \end{matrix}}{=}n\cdot 2^{n-1}

∎

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

טענה (זהות פסקל)

\begin{pmatrix} n-1 \\ k \end{pmatrix}+ \begin{pmatrix} n-1 \\ k-1 \end{pmatrix}=\begin{pmatrix} n \\ k \end{pmatrix}

הוכחה אלגברית:

\frac{(n-1)!}{k!(n-k-1)!}+\frac{(n-1)!}{(k-1)!(n-k)!}=\frac{{\color{purple}(n-k)}(n-1)!+{\color{purple}k}(n-1)!}{k!(n-k)!}=\frac{n(n-1)!}{k!(n-k)!}=\frac{n!}{k!(n-k)!}=\begin{pmatrix} n \\k \end{pmatrix}

∎

הוכחה קומבינטורית:
מצד ימין: מספר תת הקבוצות בגודל $k$ של קבוצה בגודל $n$ .
מצד שמאל: נתבונן בבניה של תת-קבוצה בגודל $k$ של קבוצה בגודל $n$ .
יהי $a$ איבר בקבוצה.

אם $a$ הוא בתת-קבוצה, נותר לבחור $k-1$ איברים מיתר $n-1$ האיברים. יש $\begin{pmatrix}n-1\\k-1\end{pmatrix}$ אפשרויות לעשות זאת.
אם $a$ לא בתת קבוצה, אז את כל $k$ האיברים נותר לבחור מיתר $n-1$ האיברים: יש $\begin{pmatrix}n-1\\k\end{pmatrix}$ אפשרויות לעשות זאת.

לפי עקרון החיבור, אם נרצה לספור כמה בסה"כ יצא לנו, אנו עוברים על כל תת הקבוצות ש- $a$ שייך אליהם ומוסיפים להם את כל תת הקבוצות ש- $a$ לא שייך אליהן.
⇐ ספרנו את מספר תת הקבוצות בגודל $k$ מתוך קבוצה בגודל $n$ .
∎

1.3.1 - משולש פסקל

\begin{array}{c} \begin{pmatrix} 0 \\ 0 \end{pmatrix} \\ \begin{pmatrix} 1 \\ 0 \end{pmatrix} \quad \begin{pmatrix} 1 \\ 1 \end{pmatrix} \\ \begin{pmatrix} 2 \\0 \end{pmatrix}\quad \begin{pmatrix} 2\\1 \end{pmatrix}\quad \begin{pmatrix} 2 \\ 2 \end{pmatrix} \\ \begin{pmatrix} 3 \\ 0 \end{pmatrix}\quad \begin{pmatrix} 3 \\ 1 \end{pmatrix}\quad \begin{pmatrix} 3 \\ 2 \end{pmatrix} \quad \begin{pmatrix} 3 \\ 3 \end{pmatrix} \end{array}

נסתכל על הערכים של המשולש:

\begin{array}{c} 1 \\ 1 \quad 1 \\ 1 \quad 2 \quad 1 \\ 1 \quad 3 \quad 3 \quad 1 \\ 1 \quad 4 \quad 6 \quad 4 \quad 1 \\ 1 \quad 5 \quad 10 \quad 10 \quad 5 \quad 1 \end{array}

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

1.4 - מספרי קטלן

1.4.0 - הקדמה

נרצה כעת להגדיר מחרוזות של סוגריים כגון ()(()) או (())( ולקבוע אילו מהן חוקיות ולא חוקיות.
נגדיר קבוצת מחרוזות $S$ מעל הא"ב $\left\{ (,) \right\}$ באינדוקציה:

בסיס: מחרוזת ריקה.
פונקצית יצירה: $\begin{matrix}F_{1}(u)=(u)\\ F_{2}(u,v)=uv\end{matrix}$

דוגמה

1.
2. $()\impliedby F_{1}(.1)$
3. $(())\impliedby F_{1}(.2)$
4. $()(()) \impliedby F_{2}(.2,.3)$
5. $(())()\impliedby F_{2}(.3,.2)$

משפט

תהי $w$ מחרוזת כלשהי.

\begin{align*} \R{\text{ מקיימת את התנאים הבאים:}} w & \iff w \in S \\ \#_{(}(w)=\#_{)}(w) \quad & .1 \\ \#_{(}(w')\geq\#_{)}(w') \;:w'\R{\text{בכל רישא ממש של }}\quad & .2 \end{align*}

סימון: כדי לא להתבלבל, במקום ) נכתוב $a$ ובמקום ( נכתוב $b$ . כלומר, $(())()=aabbab$

הוכחה:
⇐: נניח $w \in S$ . נראה כי $w$ מקיימת את $1,2$ באמצעות אינדוקציית מבנה.
בסיס: במחרוזת הריקה $\#_{a}=\#_{b}=0$ ובנוסף אין רישות ממש(ולכן, 2 מתקיים באופן ריק).
צעד: עבור $w=aw'b\impliedby w=F_{1}(w')$ ונניח נכונות ל- $w'$ .
(1): לפי הנחת האינדוקציה $\#_{a}(w')=\#_{b}(w')$ ולכן $\#_{a}(aw'b)=\#_{b}(aw'b)$ .
(2): נתבונן ברישא ממש של $w$ .

אם מדובר במחרוזת ריקה, אז $\#_{a}=\#_{b}=0$ .
אם $a$ אז $\#_{a}=1>\#_{b}=0$ .
אחרת: $au$ כאשר $u$ היא רישא ממש של $w'$ .
מהנחת האינדוקציה, $\#_{a}(u)\geq\#_{b}(u)$ ולכן $\#_{a}(au)>\#_{b}(au)$ .

עבור $w=uv\impliedby w=F_{2}(u,v)$ ונניח נכונות ל- $u,v$ .
(1): לפי הגדרת שרשור:

\#_{a}(w)=\#_{a}(u)+\#_{a}(v)\underset{\begin{matrix} \downarrow \\ \R{\text{הנחת האינדוקציה}} \end{matrix}}{=}\#_{b}(u)+\#_{b}(v)=\#_{b}(w)

(2): נתבונן ברישא $w'$ של $w$ .

אם $w'$ רישא של $u$ , אז, מהנחת האינדוקציה על $u$ : 2 מתקיים.
אם $w'=u$ אז $\#_{a}(w')=\#_{b}(w')$ מההנחה על $u$ .
אם $w'=uv'$ כאשר $v'$ היא רישא ממש של $v$ :
$\#_{a}(uv')=\#_{a}(u)+\#_{a}(v')\underset{\begin{matrix} \downarrow \\ \R{\text{מה.א. על u}} \end{matrix}}{=} \#_{b}(u)+\#_{a}(v') \underset{\begin{matrix} \downarrow \\ \R{\text{מה.א. על v}} \end{matrix}}{\geq} \#_{b}(u)+\#_{b}(v')=\#_{b}(uv')$

⇒: תהי $w$ מחרוזת שמקיימת את שני התנאים. נוכיח באינדוקציה על $n$ - מספר ה- $a,b$ שמופיע ב- $w$ כי $w \in S$ .
בסיס: $n=0$ ולכן $w$ היא המחרוזת הריקה ומהגדרת הבסיס של $S$ מתקיים $w \in S$ .
צעד: נניח כי כל מילה שמקיימת $1,2$ ויש בה $n$ זוגות $a,b$ היא ב- $S$ . תהי $w$ מילה עם $n+1$ זוגות $a,b$ המקיימת $1,2$ .
מכיוון ש- $w$ מקיימת את $2$ אז $w$ מתחילה ב- $a$ . נפרק את $w$ לשני חלקים: $w=uv$ כך ש- $u$ היא מילה באורך מינימלי(גדול מ-0) עבורה $\#_{a}(u)=\#_{b}(u)$ . נשים לב כי בניגוד ל- $u$ , המילה $v$ יכולה להיות ריקה.
מכיוון ש- $w$ מתחילה ב- $a$ מתקיים כי $u$ גם כן מתחילה ב- $a$ . נשים לב כי בכל רישא ממש של $u$ מתקיים $\#_{a}(u)>\#_{b}(u)$ .

הערה (למה?)

$u$ היא הפעם הראשונה שבה מספר ה- $a$ -ים ומספר ה- $b$ -ים זהה ולכן, כל רישא ממש שלה תהיה עם פחות $b$ -ים מ- $u$ .

לכן, האות האחרונה ב- $u$ חייבת להיות $b$ . לכן, $u=au'b$ .
⇐ מכיוון ש- $\#_{a}(u)=\#_{b}(u)$ מתקיים $\#_{a}(u')=\#_{b}(u')$ . נתבונן ברישא ממש $u''$ של $u'$ .
באותה הדרך כמו ממקודם, נקבל כי $\#_{a}(au'')>\#_{b}(au'')$ כי $au''$ רישא ממש של $u$ . לכן, $\#_{a}(u'')\geq\#_{b}(u'')$ .
⇐ הרישא $u'$ מקיימת את $1$ ו- $2$ ובנוסף, היא קצרה מ- $w$ ⇐ לפי הנחת האינדוקציה, $u' \in S$ . מכאן ש- $u \in S\impliedby u=F_{1}(u')$ .
כעת נתבונן ב- $v$ :

\#_{a}(v)=\#_{a}(w)-\#_{a}(u)\underset{\begin{matrix} \downarrow \\ \R{\text{הגדרות u,w}} \end{matrix}}{=}\#_{b}(w)-\#_{b}(u)=\#_{b}(v)

מכאן שתנאי $1$ מתקיים. כעת, נעבור לתנאי $2$ :
תהי $v'$ רישא ממש של $v$ :

\#_{a}(v')=\#_{a}(uv')-\#_{a}(u)\underset{\begin{matrix} \downarrow \\ \R{\text{הוכחה ממקודם}} \\ \#_{a}(u)=\#_{b}(u) \end{matrix}}{=}\#_{a}(uv')-\#_{b}(u)\underset{\begin{matrix} \downarrow \\ \R{\text{w מקיימת את 2}} \\ \R{\text{'vu רישא ממש של w}} \end{matrix}}{\geq}\#_{b}(uv')-\#_{b}(u)=\#_{b}(v')

ומכאן שתנאי $2$ מתקיים.
ראינו כי $w=uv$ כאשר $u \in S$ ומהנחת האינדוקציה על $v$ מתקיים $v \in S$ ומכאן $w=F_{2}(u,v)$ עבור $u,v \in S$ ולכן $w \in S$ .
∎

כעת, נרצה לספור את כמות הסוגריים המאוזנים שיש. נסמן ב- $S_{n}$ כך ש- $S_{n}\subseteq S$ עם $n$ זוגות סוגריים בדיוק.
נרצה לחשב את $|S_{n}|$ ונסמנו $c_{n}$ .

דוגמה

c_{1}=|\left\{ () \right\}|=1

c_{2}=|\left\{ ()(),(()) \right\}|=2

c_{3}=\left| \left\{ ()()(),(())(),()(()),((())),(()()) \right\} \right|=5

נרצה לדעת איך למצוא את המספר הזה באופן כללי.

הגדרה

\R{\text{מחרוזות עם n פעמים a ו-n פעמים b}}=X_{n}

S_{n}\R{\text{ שאינן ב-}}X_{n}\R{\text{מחרוזות מ-}}=Y_{n}

נשים לב כי $S_{n}\subseteq X_{n}$ ובנוסף $\begin{matrix}Y_{n}=X_{n}\setminus S_{n}\\S_{n}=X_{n}\setminus Y_{n}\end{matrix}$ .

הגדרה

(n-1)\cdot b,(n+1)\cdot a\R{\text{מחרוזות עם }}=Z_{n}

את העוצמה של הקבוצה הזו אנו כבר יודעים לחשב:

|Z_{n}|=\begin{pmatrix} 2n \\ n+1 \end{pmatrix}

נראה כי $|Z_{n}|=|Y_{n}|$ ואז מכיוון שהן שוות עוצמה נקבל כי $|S_{n}|=|X_{n}|-|Y_{n}|=\begin{pmatrix}2n\\n\end{pmatrix}-\begin{pmatrix}2n\\n+1\end{pmatrix}$ .

הוכחה:
נציג $f:Y_{n}\to Z_{n}$ חח"ע ועל וכך נוכיח את הטענה. (זוכרים את המשפט הזה ממתקא?)
נתבונן ב- $y \in Y_{n}$ המורכבת כך $y=y_{1}y_{2}\dots y_{k}y_{k+1}\dots y_{2n}$ .
נגדיר רישא מינימלית רעה: $\#_{a}<\#_{b}$ .
נגדיר: $f(y)=\overline{y_{1}}\ \overline{y_{2}}\dots \overline{y_{k}}\ y_{k+1}\dots y_{2n}$ כאשר $\begin{matrix}\overline{a}=b \\ \overline{b}=a\end{matrix}$

דוגמה

y=abba \implies f(y)=baaa

אבחנה: ברישא מינימלית רעה $\#_{b}=\#_{a}+1$ . (לו היה גדול ביותר מ- $1$ היא לא הייתה מינימלית)
⇐ ב- $f(y)$ אנו מגדילים ב- $1$ את מספר ה- $a$ והקטנו ב- $1$ את מספר ה- $b$ . נקבל כי במחרוזת כולה יש כעת $(n+1)\cdot a$ ו- $(n-1)\cdot b$ ולכן $f(y)\in Z_{n}$ .
הראנו כי זו אכן פונקציה מ- $Y_{n}$ ל- $Z_{n}$ ונראה כעת כי היא חח"ע ועל.
על: תהי $z \in Z_{n}$ . אזי: $z=z_{1}z_{2}\dots z_{k}z_{k+1}\dots z_{2n}$ . תהי $z'$ רישא מינימלית שבה $\#_{a}>\#_{b}$ . חייבת להיות כזאת, כי ב- $z$ מתקיים $\#_{a}>\#_{b}$ . מכיוון ש- $z'$ היא מינימלית: $\#_{a}=\#_{b}+1$ . (בדומה לטיעון הקודם)
נחליף כל $z_{i}$ ב- $\overline{z_{i}}$ ב- $z'$ ונקבל מחרוזת עם $n\cdot a$ ו- $n\cdot b$ (משיקולים דומים לטיעון קודם), ובה רישא "רעה" ⇐ מחרוזת $y$ ב- $Y_{n}$ עבורה $f(y)=z$ . לכן, לפי הגדרה, $f$ על.
חח"ע: יהיו $y,y'$ מחרוזות שונות ב- $Y_{n}$ . נראה כי $f(y)\neq f(y')$ .

y\neq y'\implies \exists\ i: y_{i}\neq y'_{i}

אם הרישא הרעה המינימלית של $y$ ו- $y'$ היא באורך זהה ⇐ ב- $f(y),f(y')$ מתקיים $f(y)_{i}\neq f(y')_{i}$ . (אם ה- $i$ בתוך הרישא אנחנו מחליפים $b$ ב- $a$ ולהיפך ואם ה- $i$ לא בתוך הרישא אז בכל מקרה זה מתקיים) ⇐ $f(y)\neq f(y')$ .
אחרת: הרישא הרעה המינימלית של $y,y'$ היא באורך שונה, אז ב- $f(y),f(y')$ הרישות הרעות המינימליות הן גם באורך שונה. (רישא רעה ב- $f(y)$ : הרישא המינימלית בה $\#_{b}<\#_{a}$ ) מכאן ש- $f(y)\neq f(y')$

לכן, $f$ חח"ע ועל ⇐ $|Z_{n}|=|Y_{n}|$ .
∎

1.4.1 - הגדרה

הגדרה 5 (מספר קטלן)

c_{n}=|S_{n}|=|X_{n}|-|Y_{n}|=\begin{pmatrix} 2n \\ n \end{pmatrix}-\begin{pmatrix} 2n \\ n+1 \end{pmatrix}

הערה

ההגדרה $c_{n}=\begin{pmatrix}2n\\n\end{pmatrix}-\begin{pmatrix}2n\\n+1\end{pmatrix}$ שקולה להגדרה $c_{n}=\begin{pmatrix}2n\\n\end{pmatrix}-\begin{pmatrix}2n\\n-1\end{pmatrix}$

הערה

מספרי קטלן סופרים עוד הרבה דברים, כגון:

לוח $n\times n$ . נביט באלכסון שלו ונסתכל על מסלולים שמגיעים מהנקודה $(0,0)$ לנקודה $(n,n)$ רק במעברים ימינה ולמעלה. בנוסף נגדיר שהמסלול לא יכול לעבור את האלכסון.

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

2 - עקרון שובך היונים

2.1 - העקרון הבסיסי

משפט (שובך היונים, גרסה פשוטה)

אם יש $n$ שובכים ובתוכם $n+1$ יונים, אזי ישנו שובך שיש בו יותר מיונה אחת.

הוכחה:
נניח בשלילה שכל שובך הוא ריק או עם יונה אחת ⇐ מספר היונים הוא לכל היותר $n$ . סתירה לכך שיש לנו $n+1$ יונים.
∎

משפט (גרסה פורמלית לגרסה הפשוטה של שובך היונים)

אם $|A|=n$ ו- $|B|=n+1$ אז $f:B\to A$ אינה חח"ע.

דוגמה

במגירה 10 זוגות גרביים: 5 זוגות לבנים ו-5 זוגות שחורים.
כמה גרביים צריך להוציא מהמגירה כדי שבוודאות יהיה בידינו זוג תואם?

נקצה שני שובכים: אחד ללבנים ואחד לשחורים. לכן, אם נקח 3 גרביים, שניים מהם ימופו לאותו השובך.

דוגמה

נתונה הקבוצה: $\left\{ 0,1,\dots,9 \right\}$ . נדרש להוכיח כי אם נבחר 6 מספרים מהקבוצה, יהיו זוג מספרים שסכומם 9.

הוכחה:
הקבוצה בנויה מזוגות שסכומם 9 והם: $\begin{matrix}0&-&9&&2&-&7&&5&-&4\\1&-&8&&3&-&6\end{matrix}$ .
נקצה שובך לכל זוג. לכל מספר, ישנו שובך יחיד שהוא שייך אליו. (לדוגמה 2 שייך ל- $2-7$ ). אם נקח שישה מספרים ונשים כל מספר בשובך שמתאים לו ⇐ לפי עקרון שובך היונים, מובטח שישנו שובך שבו נמצאים שני איבריו. סכומם $9$ כנדרש.
∎

2.2 - הכללות העקרון

משפט (הכללות)

אם יש $n$ שובכים ו- $m>n$ יונים, אז ישנו שובך שיש בו יותר מיונה אחת.
אם יש $n$ שובכים ו- $n\cdot k+1$ יונים לפחות, אז ישנו שובך שיש בו יותר מאשר $k$ יונים.
אם יש $n$ שובכים ו- $m$ יונים, אז ישנו שובך לפחות $\lceil \frac{m}{n}\rceil$ יונים.

דוגמה

ישנן $98$ הרצאות לשיבוץ לאורך $8$ שעות. לכמה חדרי לימוד נזדקק לכל הפחות?

ההרצאות הן היונים והשעות הן השובכים. לפי עקרון שובך היונים המוכלל (ספציפית, סעיף 3), אזי קיימת שעה שבה יש לפחות $\lceil \frac{98}{8}\rceil=13$ .
אם כך, נדרש ללפחות $13$ חדרי לימוד.

דוגמה

תהי $A=\left\{ 1,2,\dots,150 \right\}$ (כאשר $A \subseteq \mathbb{N}$ ). נרצה לבחור 25 מספרים שונים מתוך $A$ . נדרש להוכיח שישנם 2 זוגות מתוך 25 המספרים בעלי סכום שווה.

הוכחה:
הסכומים של 2 מספרים נעים בין $3$ לבין $299$ (זאת מכיוון ש- $1+2=3,149+150=299$ )
אם אנו לוקחים $25$ מספרים שונים, מספר הסכומים הוא כמספר האפשרויות לבחור זוג מספרים מתוך ה- $25$ . לכן, מספר הסכומים הוא $\begin{pmatrix}25\\2\end{pmatrix}$ .

\begin{pmatrix} 25 \\2 \end{pmatrix}=\frac{25!}{2!23!}=\frac{24\cdot 25}{2}=25\cdot 12=300

יש לנו $300$ זוגות שונים. אלו יהיו היונים שלנו. נשים אותם בשובכים שיהיו הסכומים שלנו. ישנן יותר זוגות מאשר סכומים ולכן, לפי הכללת שובך היונים, יש $2$ זוגות שונים בעלי אותו הסכום.
∎

2.2.1 - משפט ארדש-סקרש

משפט (ארדש-סקרש)

בסדרה של מספרים שונים זה מזה באורך $n^2+1$ , ישנה סדרה עולה באורך $n+1$ לפחות או סדרה יורדת באורך $n+1$ לפחות.

דוגמה

עבור $n=3$ . נקח סדרה באורך $10$ . הנה עשרה מספרים באופן אקראי לגמרי:

\begin{matrix}12&7&19&2&0&6&22&14&9&15\end{matrix}

ננסה למצוא סדרה עולה/יורדת באורך 4 לפחות.
נוכל למצוא את הסדרה העולה: $0,6,9,15$ .

הוכחה:
נניח בשלילה כי קיימת סדרה באורך $n^2+1$ כאשר הסדרה היורדת/עולה הארוכה ביותר היא באורך $n$ .
לכל $a_{i}$ (כאשר $1\leq i\leq n^2+1$ ) נצמיד שני ערכים:

\begin{matrix} a_{i}\R{\text{אורכה של סדרה עולה ארוכה ביותר שמתחילה ב-}} & :b_{i} \\ a_{i}\R{\text{אורכה של סדרה יורת ארוכה ביותר שמתחילה ב-}} & :c_{i} \end{matrix}

לפי ההנחה, ערך $b_{i}$ המקסימלי הוא $n$ וערך $c_{i}$ המקסימלי הוא $n$

1\leq b_{i}\leq n,\quad 1\leq c_{i}\leq n\quad \impliedby

לכן, ישנם לכל היותר $n^2$ זוגות ערכי $(b_{i},c_{i})$ שונים. מכיוון שישנם $n^2+1$ איברי סדרה ⇐ לפי עקרון שובך היונים, ישנם שני איברים, $a_{i}$ ו- $a_{j}$ כאשר $i<j$ כך ש- $\begin{matrix}b_{i}=b_{j},&c_{i}=c_{j}\end{matrix}$ .
אם $a_{i}<a_{j}$ ומ- $a_{j}$ מתחילה סדרה עולה באורך $b_{j}$ , הוספת $a_{i}$ בתחילת הסדרה יוצרת סדרה עולה באורך $b_{j}+1$ . מכאן $b_{i}>b_{j}$ - סתירה.
אם $a_{i}>a_{j}$ , באופן דומה, נוסיף את $a_{i}$ כאיבר ראשון בסדרה יורת באורך $c_{j}+1$ שמתחילה ב- $c_{i}>c_{j}\impliedby a_{i}$ - סתירה.
לכן, ישנה סדרה עולה/יורדת באורך $n+1$ .
∎

3 - עקרון הכלה-הדחה

כעת, נרצה לספור כמה איברים יש בקבוצות של איחוד. לשם כך, נגלה את עקרון ההכלה-הדחה.
יהיו $A_{1},\dots,A_{n}$ ואנו נרצה לחשב את $|A_{1} \cup\dots \cup A_{n}|$ . הבעיה היא שאם יש איברים משותפים בין הקבוצות אנו רוצים לא לספור אותם פעמיים.
Drawing 2026-04-10 15.57.11.excalidraw.svg
נדרש לבצע $|A_{1}\cup A_{2}|=|A_{1}|+|A_{2}|-|A_{1}\cap A_{2}|$ .
מה קורה כאשר יהיו שלוש קבוצות?
קומבינטוריקה מהסרטונים של שרי 2026-04-10 15.58.33.excalidraw.svg

|A_{1}\cup A_{2}\cup A_{3}|=|A_{1}|+|A_{2}|+|A_{3}|-|A_{1}\cap A_{2}|-|A_{2}\cap A_{3}|-|A_{1}\cap A_{3}|+|A_{1}\cap A_{2}\cap A_{3}|

כעת, באופן כללי:

משפט (נוסחת הכלה-הדחה)

יהיו $A_{1},\dots,A_{n}$ קבוצות.

|A_{1}\cup\dots \cup A_{n}|=\sum_{i=1}^n |A_{i}|-\sum_{1\leq i_{1}< i_{2}\leq n}|A_{i_{1}}\cap A_{i_{2}}|+\sum_{1\leq i_{1}< i_{2}< i_{3}\leq n}|A_{i_{1}}\cap A_{i_{2}}\cap A_{i_{3}}|+\dots

+(-1)^{k+1}\sum_{1\leq i_{1}<i_{2}<\dots<i_{k}\leq k}|A_{1}\cap A_{2}\cap\dots \cap A_{i_{k}}|+\dots

נראה כעת כי הנוסחה נכונה. כלומר, כל $a \in A_{1}\cup\dots \cup A_{n}$ נספר בדיוק פעם אחת.
נניח ש- $a$ שייך ל- $t$ קבוצות באיחוד (מתוך $n$ ). $a$ נספר בכל פעם ששייך לכל הקבוצות בחיתוך.
⇐ בכל חיתוך של מעל $t$ קבוצות: $a$ לא שייך ולא נספר. בשאר החיתוכים, $a$ נספר אם נבחרות $k$ קבוצות מתוך $t$ הקבוצות.
⇐ סה"כ נספר:

\sum_{k=1}^t \begin{pmatrix} t \\ k \end{pmatrix} (-1)^{k+1}

נרצה להראות שהביטוי $1=$ .

\begin{align*} & \sum_{k=1}^t \begin{pmatrix} t \\ k \end{pmatrix}(-1)^{k+1}=-\sum_{k=1}^t \begin{pmatrix} t \\ k \end{pmatrix}(-1)^k \underset{\begin{matrix} \downarrow \\ \begin{pmatrix} t \\ 0 \end{pmatrix}(-1)^0=1:k=0\R{\text{עבור }} \\ \R{\text{+המקדם: 1-}} \end{matrix}}{=} 1-\sum_{k=0}^t \begin{pmatrix} t \\ k \end{pmatrix}(-1)^t \\ & =1-\underbrace{\sum_{k=0}^t \begin{pmatrix} t \\ k \end{pmatrix}(-1)^k \cdot 1^{t-k}}_{\begin{matrix} \R{\text{זוהי בדיוק נוסחת הבינום}} \\ (-1+1)^{t}=0 \end{matrix}} =1-0=1 \end{align*}

הנוסחה שפיתחנו נקראת נוסחת ההכלה-הדחה (או הכלה-הפרדה).

דוגמה

בחפיסת קלפים ישנם $52$ קלפים. מתוכם, יש $4$ מלכים, $4$ מלכות, $4$ נסיכים ו- $4$ קלפי אסים.
ביד ברידג' ישנם $13$ קלפים. כמה ידיים שונות יש? יש בדיוק $\begin{pmatrix}52\\13\end{pmatrix}$ ידיים שונות.
בכמה מהיידים הנ"ל יש לפחות קלף מלוכה אחד מכל סוג?

נחשב את הקבוצה המשלימה. כלומר, את מספר הידיים בהן אחד מסוגי המלוכה חסר.
נגדיר את הקבוצות הבאות:

\begin{align*} \R{\text{כל הידיים ללא קלפי מלכה}} & :A_{1} \\ \R{\text{כל הידיים ללא קלפי מלך}} & :A_{2} \\ \R{\text{כל הידיים ללא קלפי נסיך}} & :A_{3} \\ \R{\text{כל הידיים ללא קלפי אס}} & :A_{4} \end{align*}

האיחוד $A_{1}\cup A_{2}\cup A_{3}\cup A_{3}$ הוא היידים הרעות.
נחשב את עוצמת האיחוד לפי עקרון ההכלה-הדחה:

|A_{1}\cup \dots \cup A_{4}|=\underbracket{4\cdot\begin{pmatrix} 48 \\ 13 \end{pmatrix}}_{\begin{align*} |A_{1}|+|A_{2}| \\ +|A_{3}|+|A_{4}| \end{align*}}-\underset{\begin{matrix} \downarrow &&& \\ \R{\text{שני סוגים שמתוכם}} \\ \R{\text{אסור לבחור}} \end{matrix}}{\begin{pmatrix} 4 \\ 2 \end{pmatrix}\begin{pmatrix} 44 \\ 13 \end{pmatrix}}+\underset{\begin{matrix} \downarrow &&& \\ \R{\text{3 סוגים שמתוכם}} \\ \R{\text{אסור לבחור}} \end{matrix}}{\begin{pmatrix} 4 \\ 3 \end{pmatrix}\begin{pmatrix} 40 \\ 13 \end{pmatrix}}-{\begin{pmatrix} 4 \\ 4 \end{pmatrix}\begin{pmatrix} 36 \\ 13 \end{pmatrix}}=t

⇐ מספר הידיים הטובות הוא $\begin{pmatrix}52\\13\end{pmatrix}-t$

הערה

מה רע בפתרון הבא? נבחר קלף אחד מכל סוג מלוכה, ונבחר 9 קלפים מבין הקלפים שנותרו.

\binom{4}{1}\binom{4}{1}\binom{4}{1}\binom{4}{1}\binom{48}{9}

תשובה: החישוב לא נכון. אם נקח יד שיש בה שני נסיכים, היא תחושב יותר מפעם אחת: פעם אחת בוחרים את הנסיך הראשון בבחירה מתוך והנסיכים ואת השני מכל היתר ופעם אחת הפוך.

3.1 - דוגמה עם נקודות שבת

נתבונן ב- $\left\{ 1,2,\dots,n \right\}$ . סידור של איברי הקבוצה נקרא תמורה.

דוגמה

$\left\{ 1,2,3,4 \right\}$ - תמורה אפשרית: $2,1,3,4$ .

כמה תמורות אפשריות יש לקבוצה $\left\{ 1,2,\dots,n \right\}$ ? זהו סידור ללא חזרות ועם חשיבות לסדר ולכן $n!$ .
נוכל חשוב על כל תמורה כזו כפונקציה חח"ע ועל מהפונקציה לעצמה - $f:\left\{ 1,2,\dots,n \right\}\to \left\{ 1,2,\dots ,n \right\}$ .

דוגמה

בדוגמה ממקודם: $f(1)=2,f(2)=1,f(3)=3,f(4)=4$ .

הגדרה 6 (נקודת שבת)

איבר $i$ הוא נקודת שבת אם $f(i)=i$ .

דוגמה

בדוגמה ממקודם $3,4$ הן נק' שבת.

בכמה תמורות של $\left\{ 1,\dots,n \right\}$ אין נקודות שבת?
רעיון: נחשב בכמה מהתמורות יש לפחות נקודת שבת אחת, ונחסר מכלל התמורות( $n!$ )
נגדיר: $A_{i}$ קבוצת התמורות של $\left\{ 1,\dots,n \right\}$ בהן $i$ נקודת שבת.

|A_{i}|=(n-1)!

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

n!-|A_{1}\cup\dots \cup A_{n}|=n!-\begin{pmatrix} n \\ 1 \end{pmatrix}(n-1)!+\begin{pmatrix} n \\ 2 \end{pmatrix}(n-2)!+\dots+(-1)^{k}\begin{pmatrix} n \\ k \end{pmatrix}(n-k)!+\dots

n!-|A_{1}\cup\dots \cup A_{n}|=\boxed{\sum_{k=0}^n (-1)^k \begin{pmatrix} n \\ k \end{pmatrix}(n-k)!}

אנחנו לא נפשט את הביטוי יותר (לטענת שרי הוא יפה גם ככה)

3.2 - הכללת העקרון

תהי $A$ קבוצה ויהיו $p_{1},p_{2},\dots,p_{n}$ תכונות אפשריות של איברי $A$ . כלומר, כל $a \in A$ מקיים תת-קבוצה של $\left\{ p_{1},\dots,p_{n} \right\}$ (יתכן שאף תכונה).
נסמן: $A_{i}$ - קבוצת האיברים המקיימים את $p_{i}$ .
מהי קבוצת האיברים המקיימים את כל התכונות? $\bigcap_{1\leq i\leq n}A_{i}$ .
מהי קבוצת האיברים הלא מקיימים אף תכונה? $A \setminus \bigcup_{1\leq i\leq n}A_{i}$ . - את מספר האיברים ניתן לחשב בעזרת הכלה-הדחה.
נתבונן ב- $\left\{ p_{i_{1}},p_{2},\dots,p_{i_{k}} \right\}$ ⇐ קבוצת האיברים המקיימים את כל התכונות הללו היא $\bigcap_{1\leq i\leq k}A_{i}$ וקבוצת האיברים שלא מקיימים אף תכונה מהן היא $A \setminus \bigcup_{1\leq i\leq k}A_{i}$ .

הגדרה (סימון)

$E(m)$ הוא מספר האיברים המקיימים בדיוק $m$ תכונות.

דוגמה

E(0)=|A|-\left| \bigcup_{i=1}^n A_{i} \right|

E(n)=\left| \bigcap_{i=1}^n A_{i} \right|

טענה

נסמן $=w(i)$ המחובר ה- $i$ בהכלה-הדחה.

E(m)=\begin{pmatrix} m \\ m \end{pmatrix}w(m)-\begin{pmatrix} m+1 \\ m \end{pmatrix}w(m+1)+\dots+(-1)^{m+n}\begin{pmatrix} n \\ m \end{pmatrix}w(n)

הערה

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

דוגמה

נתונים $n$ סלים שונים ו- $x$ כדורים שונים. בכמה דרכים ניתן לפזר את הכדורים בסלים כך שיש בדיוק $k$ סלים ריקים?

נגדיר: $p_{i}$ - הסל ה- $i$ ריק ו- $A_{i}$ היא קבוצת הסידורים שבהם התא ה- $i$ ריק.

|A_{i}|=(n-1)^x

חיתוך בין כמה קבוצות מסמל אוסף של תאים ריקים:

\left| \bigcap_{i=1}^k A_{i} \right|=(n-k)^x

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

E(k)=\begin{pmatrix} k \\ k \end{pmatrix}\begin{pmatrix} n \\ k \end{pmatrix}(n-k)^x-\begin{pmatrix} k+1 \\ k \end{pmatrix}\begin{pmatrix} n \\ k+1 \end{pmatrix}(n-k-1)^x+\dots+(-1)^{k+n}\begin{pmatrix} n \\ k \end{pmatrix}\begin{pmatrix} n \\ n \end{pmatrix}(n-n)^x

דוגמה (לדוגמה)

נקח מקרה פרטי שבו $x=n$ ואנחנו מבקשים $k=0$ סלים ריקים. זה משאיר לנו רק את האופציה להכניס כדור אחד לכל סל. זה שקול למספר הסידורים השונים של $n$ כדורים. כלומר, מספר התמורות בגודל $n$ שזה $n!$ .
לפי הנוסחה:

E(0)=\begin{pmatrix} 0 \\ 0 \end{pmatrix}\begin{pmatrix} n \\ 0 \end{pmatrix}(n-0)^n-\begin{pmatrix} 1 \\ 0 \end{pmatrix}\begin{pmatrix} n \\ 1 \end{pmatrix}(n-1)^n+\dots+(-1)^n\begin{pmatrix} n \\ 0 \end{pmatrix}\begin{pmatrix} n \\ n \end{pmatrix}(n-n)^n

=\sum_{k=0}^n \begin{pmatrix} n \\ k \end{pmatrix}(n-k)^n (-1)^k \underset{\begin{matrix} \downarrow \\ \R{\text{מתברר}} \end{matrix}}{=}n!