אינדוקציה

אינדוקציה הוא אוסף של טענות המוגדרות על כל המספרים הטבעיים.
נתחיל כעת באינדוקציה בתור קונספט: נתונה טענה $\mathcal{A}(n)$ התלויה בפרמטר טבעי(חיובי) $n$ .

דוגמה

מספר האפשרויות לסדר $n$ מספרים שונים בשורה הוא $P_{n}=n!$
מספר האפשרויות לסדר 3 מספרים שונים בשורה הוא $\mathcal{A}(3):\qquad P_{3}=6$

דוגמה

בלוח $n\times n$ יש $S_{n}=\frac{n(n+1)(2n+1)}{6}$ ריבועים.
בלוח $6\times 6$ יש $S_{6}=91=\frac{6(6+1)(2\cdot 6+1)}{6}$ ריבועים.

אקסיומה

תהי טענה $\mathcal{A}(n)$ התלויה בפרמטר טבעי(חיובי) $n$ . אם:

הטענה $\mathcal{A}(1)$ נכונה $\color{green}(\R{\text{בסיס האינדוקציה}})$
לכל $n$ מתקיים כי נכונות $\mathcal{A}(n)$ גוררת את נכונות ${\color{purple}(\R{\text{צעד האינדוקציה}})}\quad\mathcal{A}(n+1)$ .

אזי, הטענה $\mathcal{A}(n)$ נכונה לכל $n$ .

דוגמה

טענה

בלוח $n\times n$ יש $S_{n}=\frac{n(n+1)(2n+1)}{6}$ ריבועים.

הוכחה: נוכיח את הטענה באינדוקציה
בסיס: נוכיח את הטענה עבור $n=1$
מספר הריבועים בלוח $1\times1$ הוא $S_{1}=1=\frac{1\cdot 2\cdot 3}{6}$ .
צעד: נניח כי הטענה נכונה עבור $n$ ונוכיח כי הטענה נכונה עבור $n+1$ .
קיימת פונקציה חח"ע ועל בין מספר הקודקודים בריבוע $n\times n$ לבין מספר הריבועים הנוספים שנדרש להוסיף כשעבור מריבוע $n\times n$ לריבוע $n+1\times n+1$ .
לכן מתקיים:

S_{n+1}=S_{n}+(n+1)^2=\frac{n(n+1)(2n+1)}{6}\!+(n+1)^2\!=\!\frac{n+1}{6}(n(2n+1)+6(n+1))\!=\!\frac{n+1}{6}(n+2)(2n+3)

∎

משפט

תהי $\mathcal{A}(n)$ התלויה בפרמטר טבעי(חיובי) $n$ . אם

הטענה $\mathcal{A}(1)$ נכונה
לכל $n$ מתקיים כי נכונות כל הטענות $\mathcal{A}(n),\dots,\mathcal{A}(2),\mathcal{A}(1)$ גוררת את נכונות $\mathcal{A}(n+1)$

אזי, הטענה $\mathcal{A}(n)$ נכונה.

המשפט הזה נראה לכאורה חלש יותר מהאקסיומה ממקודם - נוכל להגיע ממנו לאקסיומה על ידי שינוי הטענה:
נגדיר טענה $\mathcal{B}(n)$ בתור: "כל הטענות $\mathcal{A}(n),\dots,\mathcal{A}(2),\mathcal{A}(1)$ " נכונות"

הטענה $\mathcal{B}(1)$ נכונה.
לכל $n$ מתקיים: נכונות $\mathcal{B}(n)$ גוררת את נכונות $\mathcal{A}(n+1)$ ולכן את נכונות $\mathcal{B}(n+1)$ .

מהאקסיומה נובע כי $\mathcal{B}(n)$ נכונה לכל $n$ .

דוגמה

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

טענה

לכל טבעי חיובי $n$ , מספר הצמתים בכל עץ חלוקה בינארי $n$ הוא $2n-1$ .

הוכחה: נוכיח את הטענה באינדוקציה.
בסיס: ברור
צעד: נניח כי הטענה נכונה עבור $n,\dots,2,1$ ונוכיח כי הטענה נכונה עבור $n+1$ .
נגדיר את שני הילדים של השורש בעץ החדש כ: $n_{1},n_{2}$ . לפי הגדרת עץ חלוקה בינארי נקבל:

n_{1}+n_{2}=n+1 \qquad \qquad n_{1},n_{2}\geq 1

לכן, כל ילד מקיים: $n_{1},n_{2}\leq n$ . לכן, לפי הנחת האינדוקציה לעץ המתחיל מ- $n_{i}$ יש $T_{i}=2n_{i}-1$ ואז מתקיים:

T=T_{1}+T_{2}+1=(2n_{1}-1)+(2n_{2}-1)+1=2(n_{1}+n_{2})-1=2(n+1)-1

כנדרש.
∎

אינדוקציה רב מימדית

נתונה טענה $\mathcal{A}(n,m)$ התלויה במספרים טבעיים(חיוביים) $n,m$ .

דוגמה

$\mathcal{A}(n,m)$ היא הטענה הבאה: מספר האפשרויות לבחור $m$ איברים שונים ללא חזרות מתוך $n$ איברים שונים כשיש חשיבות לסדר הוא:

P_{n}^m=\frac{n!}{(n-m)!}

נזכר בזה מבעיות ספירה.

משפט

תהי $\mathcal{A}(n,m)$ טענה התלויה במספרים טבעיים חיוביים $n,m$ .
אם הטענות $\mathcal{A}(n,1)$ ו- $\mathcal{A}(1,m)$ נכונות לכל $n,m$ ו- $\mathcal{A}(n,m)$ גוררת את $\mathcal{A}(n+1,m+1)$ אזי $\mathcal{A}(n,m)$ נכונה לכל $n,m$ .

משפט

תהי $\mathcal{A}(n,m)$ טענה התלויה במספרים טבעיים חיוביים $n,m$ .
אם הטענה $\mathcal{A}(1,1)$ נכונה ו- $\mathcal{A}(n,m)$ גוררת את $\mathcal{A}(n+1,m)$ ו- $\mathcal{A}(n,m+1)$ אזי $\mathcal{A}(n,m)$ נכונה לכל $n,m$ .

רקורסיה

הגדרה 1 (נוסחת נסיגה)

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

דוגמה

סדרה חשבונית: $a_{n}=a_{n-1}+d$ כאשר $a_{1}=a$ תנאי ההתחלה ואז $a_{n}=a+(n-1)d$ .
סדרה הנדסית: $a_{n}=a_{n-1}q$ כאשר $a_{1}=a$ תנאי ההתחלה ואז $a_{n}=aq^{n-1}$ .

דוגמה

מה מספר המילים מעל $\left\{ 1,2 \right\}$ באורך כלשהו שסכום איבריהן הוא $n$ ?
נסמן ב- $a_{n}$ את מספרן:

n=5:\qquad 1,1,1,1,1 \quad 1,1,1,2 \quad 1,1,2,1 \quad 1,2,1,1 \quad 2,1,1,1 \quad 2,2,1 \quad 2,1,2 \quad 1,2,2 \implies a_{5}=8

השאלה היא איך אנו ניצור נוסחת נסיגה לזה?
כל מילה שסכומה $n$ מתחילה ב- $1$ או $2$ .
אם היא מתחילה ב- $1$ אזי נדרש ליצור את המשך המילה, שהיא מילה בפני עצמה עבור $n-1$ ואז זה יהיה $a_{n-1}$ .
באותו האופן, אם היא מתחילה ב- $2$ אז המשך המילה יהיה $a_{n-2}$ ולכן:

a_{n}=a_{n-1}+a_{n-2}

וזוהי סדרת פיבונאצ'י (המופיעה עם תנאי התחלה: $a_{1}=1,a_{2}=2$ )

בלבול - $Derangement$

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

דוגמה

D_{1}=0 \qquad \begin{matrix} D_{2}=1 \\ {\color{red}12} \\ {\color{green}21} \end{matrix} \qquad \begin{matrix} D_{3}=2 \\ {\color{red}123} \\ {\color{red}132} \\ {\color{red}213} \\ {\color{green}231} \\ {\color{green}312} \\ {\color{red}321} \end{matrix}

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

D_{n}=(n-1)(D_{n-1}+D_{n-2})

נסיגה רב-מימדית

נסמן ב- $\mathcal{A}(n,m)$ את מספר המסלולים $UR$ מ- $(0,0)$ ל- $(n,m)$ .
קומבי-הרצאה4-תמונה1.png

A(0,1)=1 \qquad \qquad A(1,0)=1 \qquad \qquad A(1,1)=2

נשים לב כי כדי להגיע ל- $(n,m)$ נדרש לעבור או ב- $(n-1,m)$ או ב- $(n,m-1)$ ולכן, מספר המסלולים הוא:

\boxed{\;\begin{matrix} \\ \\ \end{matrix}\mathcal{A}(n,m)=\mathcal{A}(n-1,m)+\mathcal{A}(n,m-1)\;}

מהו תנאי ההתחלה? כלומר, מה אנו לא יכולים לחשב?
אנו לא יכולים לחשב את כל השורה הראשונה ואת כל העמודה הראשונה.

\mathcal{A}(0,m)=\mathcal{A}(n,0)=1

ואת כל השאר ניתן לחשב.

ננסה למצוא נוסחה מפורשת. ננחש $\mathcal{A}(n,m)=\begin{pmatrix}n+m\\ m\end{pmatrix}$ ונוכיח באינדוקציה:
בסיס: $\mathcal{A}(0,m)=\mathcal{A}(n,0)=1$
צעד:

\mathcal{A}(n,m)=\mathcal{A}(n-1,m)+\mathcal{A}(n,m-1)\underset{\begin{matrix} \downarrow \\ \R{\text{הנחת האינדוקציה}} \end{matrix}}{=}\begin{pmatrix} n+m-1 \\ m \end{pmatrix}+\begin{pmatrix} n+m-1 \\ m-1 \end{pmatrix} \underset{\begin{matrix} \downarrow \\ \R{\text{זהות משולש פסקל}} \end{matrix}}{=} \begin{pmatrix} n+m \\ m \end{pmatrix}

∎

הערה

ניתן לחשוב על כל מסלול ניתן לרשום את הסדר שלו כמו וקטור בינארי(מתי ממשיכים ימינה ומתי למעלה)
אורך של מילה כזאת תהיה $n+m$ (כי אנו הולכים $n$ צעדים ימינה ו- $m$ צעדים למעלה)
לכן, כל מילה כזו יכולה להיות מוגדרת ע"י מספר הצעדים למעלה שבה באופן מסודר. שזה בדיוק בחירה ללא חזרות וכשאין חשיבות לסדר שזה $\begin{pmatrix}n+m\\ m\end{pmatrix}$ .

עקרון ההכלה וההדרה

הקדמה

הגדרה 2 (הקבוצה המשלימה)

הקבוצה $\overline{A}$ תקרא הקבוצה המשלימה של $A$ אם:

\overline{A}=\left\{ x | x \not\in A \right\}

משפט (תכונות הקבוצה המשלימה)

\begin{matrix} \overline{A}\cap A=\emptyset \\ \overline{\overline{A}}=A \\ \overline{A} \cup A=U \quad \R{\text{כאשר U היא הקבוצה האוניברסלית:}} \\ |\overline{A}|=|U|-|A| \end{matrix}

משפט (כללי דה-מורגן)

\overline{A \cup B}=\overline{A} \cap \overline{B}

\overline{ A \cap B}=\overline{A} \cup \overline{B}

הכלה והדרה

משפט

|A \cup B|=|A|+|B|-|A \cap B|

|\overline{A} \cap \overline{ B}|=|U|-(|A|+|B|)+|A \cap B|

הוכחה:

|A \cup B|=|X|+|Y|+|Z|

|A|+|B|-|A \cap B|=(|X|+|Y|)+(|Y|+|Z|)-|Y|=|X|+|Y|+|Z|

|\overline{ A}\cap \overline{B}|=|\overline{A \cup B}|=|U|-|A \cup B|=|U|-(|A|+|B|)+|A \cap B|

∎

הכלה והדרה עבור שלוש קבוצות

משפט

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

העקרון באופן כללי

נתונות $n$ תתי-קבוצות $A_{1},A_{2},\dots,A_{n}\subseteq U$ .
נסמן: $\displaystyle W_{1}=\sum_{i=1}^n |A_{i}|$

W_{2}=\sum_{1\leq i_{1}< i_{2}\leq n}|A_{i_{1}}\cap A_{i_{2}}|

\vdots

W_{k}=\sum_{1\leq i_{1}<i_{2}<\dots<i_{k}\leq n}|A_{i_{1}}\cap A_{i_{2}}\cap \dots \cap A_{i_{k}}|

\vdots

W_{n}=|A_{1}\cap A_{2}\cap\dots \cap A_{n}|=\left| \bigcap_{1\leq i\leq n} A_{i} \right|

משפט (עקרון ההכלה וההדרה)

נסמן $\displaystyle W_{k}=\sum_{1\leq i_{1}<i_{2}<\dots<i_{k}\leq n}^{\begin{matrix}\\ \end{matrix}}|A_{i_{1}}\cap A_{i_{2}}\cap\dots \cap A_{i_{k}}|$ ואז מתקיים:

\begin{align*} |A_{1}\cup A_{2} \cup A_{3}\cup\dots \cup A_{n}|=\sum_{k=1}^n (-1)^{k+1}W_{k} &\;\;.1 \\ E(0) \overset{\Tiny\triangle}{=} |\overline{A_{1}}\cap\overline{A_{2}}\cap\overline{A_{3}}\cap \dots \cap\overline{A_{n}}|=|U|-\sum_{k=1}^n (-1)^{k+1}W_{k}=\sum_{k=0}^n (-1)^k W_{k} &\;\; .2 \end{align*}

הוכחה (1):
נבדוק תרומת איבר נתון $x \in U$ לשני האגפים.
מקרה א': $x$ אינו נמצא כלל ב- $A_{1}\cup A_{2}\cup\dots \cup A_{n}$ . לכן, $x$ אינו שייך לאף $A_{i}$ ולאף $A_{i_{1}}\cap A_{i_{2}}\cap\dots \cap A_{i_{k}}$ ולכן תורם $0$ לשני האגפים.
מקרה ב': $x$ שייך ל- $m$ קבוצות בדיוק כאשר $m>0$ . נניח בה"כ כי שייך ל- $A_{1},\dots,A_{m}$ .
אזי, ל- $|A_{1}\cup A_{2}\cup\dots \cup A_{n}|$ הוא תורם 1.
נשים לב כי $x$ שיך ל- $A_{i_{1}}\cap A_{i_{2}}\cap\dots \cap A_{i_{k}}$ אמ"מ $\left\{ i_{1},i_{2},\dots,i_{k} \right\}\subseteq \left\{ 1,2,3,\dots,m \right\}$ לכן התרומה של $x$ ל- $W_{k}$ היא $\begin{pmatrix}n\\ k\end{pmatrix}$ והתרומה ל- $\sum_{k=1}^n (-1)^{k+1}W_{k}$ היא:

\sum_{k=1}^n (-1)^{k+1}\begin{pmatrix} m \\ k \end{pmatrix}=1-\sum_{k=0}^m (-1)^k \begin{pmatrix} m \\ k \end{pmatrix}\underset{\begin{matrix} \downarrow \\ \R{\text{משפט הבינום}} \end{matrix}}{=} 1-(1-1)^m=1

∎

הוכחה (2):

\begin{align*} \left| \overline{A_{1}}\cap\overline{A_{2}}\cap\overline{A_{3}}\cap \dots \cap\overline{A_{n}} \right|&= \left| U \right|-\left| \overline{\overline{A_{1}}\cap\overline{A_{2}}\cap\overline{A_{3}}\cap \dots \cap\overline{A_{n}}}\right| \\ &=W_{0}-\left| A_{1}\cup A_{2} \cup A_{3}\cup \dots \cup A_{n} \right| \\ &=W_{0}-\sum_{k=1}^n (-1)^{k+1}W_{k} \\ &=\sum_{k=0}^n (-1)^k W_{k} \end{align*}

∎

בלבול באמצעות הכלה-הדרה

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

D_{n}=\left| \overline{A_{1}}\cap \overline{A_{2}}\cap \overline{A_{3}}\cap \dots \cap \overline{A_{n}} \right|

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

D_{n}=\sum_{k=0}^n (-1)^k W_{k}

נחשב את $W_{k}$ (בזהירות). קודם כל נחשב את $W_{1}$ כדי להתחמם:

W_{1}=|A_{1}|+|A_{2}|+\dots+|A_{n}|=

$A_{1}$ - כל התמורות בהן $1$ במקום $1$ . כלומר, המקום של $1$ נקבע וסידור של שאר האיברים הוא $(n-1)!$ . כך לכל קבוצה ולכן: $|A_{i}|=(n-1)!$ ואז:

W_{1}=n(n-1)!

הערה: ברור שזה $n!$ אבל המרצה לא רצה לרשום זאת כך ותכף נראה למה.
נמשיך בזהירות שלנו ונחשב את $W_{2}$ כך:

W_{2}=|A_{1}\cap A_{2}|+|A_{1}\cap A_{3}|+\dots+|A_{n-1}\cap A_{n-2}|

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

W_{2}= \begin{pmatrix} n \\ 2 \end{pmatrix}(n-2)!

הופה, נשים לב שיש לנו איזושהי תבנית. נבנה עכשיו את $W_{k}$ הכללי:

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

כעת, נוכל לחשב את $D_{n}$ באמצעות עקרון ההכלה-הדרה:

D_{n}=\sum_{k=0}^n (-1)^k W_{k}=\sum_{k=0}^n \frac{(-1)^k n!}{k!}=n! \sum_{k=0}^n \frac{(-1)^k}{k!}=n!\sum_{k=0}^n \frac{(-1)^k}{k!} \approx \frac{n!}{e}

סיכום עד כה

דוגמה

כעת נקח $n$ כדורים ו- $r$ תאים.

\begin{array}{|c|c|c|c|} \hline \R{\text{ תאים}}r & \R{\text{ כדורים}}n & \R{\text{לכל היותר כדור אחד בכל תא}} & \R{\text{לפחות כדור אחד בכל תא}} & \R{\text{מספר כלשהו של כדורים בתא}} \\ \hline \R{\text{זהים}} & \R{\text{זהים}} & \begin{cases} 1 & r\geq n \\ 0 & r<n \end{cases} & \Pi(n,r)\!=\!\Pi(n\!-\!1,r\!-\!1)\!+\!\Pi(n\!-\!r,r) & \Pi(n+r,r) \\ \hline \R{\text{זהים}} & \R{\text{שונים}} & \begin{cases} 1 & r\geq n \\ 0 & r<0 \end{cases} & \displaystyle S(n,r)=\frac{1}{r!}T(n,r) & > \displaystyle \sum_{i=1}^r S(n,i) \\ \hline \R{\text{שונים}} & \R{\text{זהים}} & \begin{pmatrix} r \\ n \end{pmatrix} & \mathbb{C}_{r}^{n-r}=\begin{pmatrix} n-1 \\ n-r \end{pmatrix} & \mathbb{C}_{r}^{n}=\begin{pmatrix} r+n-1 \\ n \end{pmatrix} \\ \hline \R{\text{שונים}} & \R{\text{שונים}} & P_{r}^n=\begin{pmatrix} r \\ n \end{pmatrix}n! & \displaystyle T(n,r)=\sum_{k=0}^r (-1)^k\begin{pmatrix} r \\ k \end{pmatrix}(r-k)^n & r^n \\ \hline \end{array}

איך נוכל לפתור את $T(n,r)$ כנוסחת נסיגה?

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

נתחיל מהעוגן ונבחר כדור מיוחד. מה ניתן להגיד על כדור מסויים? הוא באחד מהתאים. יש לנו $r$ אפשרויות לסידור הכדור היחיד שלנו. לאחר שאנו שמים אותו בתא, הוא כבר לא ריק ולכן אין עליו מגבלה. לכן, נוספו לנו יותר אפשרויות.
נדרש להתחכם טיפה ולפצל לשני מקרים. אילו? או שהכדור יהיה לבד בתא או שיהיה בתא לפחות עוד כדור אחד.
המקרה שהכדור יהיה לבדו בתא יהיה סידור של $n-1$ כדורים ל- $r-1$ תאים והמקרה השני הינו סידור של $n-1$ כדורים ל- $r$ תאים.

T(n,r)=r(T(n-1,r)+T(n-1,r-1))

למה זה עובד? לאור תנאי העצירה של הפונקציה. אנו עוצרים כל פעם ש- $n< r$ וכל פעם שזה קורה אנו מחזירים אפס. לכן, מקרים בהם כל הכדורים נכנסים לאותו התא לא נספרים.

איך נוכל לפתור את $S(n,r)$ כנוסחת נסיגה?

נוכל לעשות אותה ישירות כבעיה חדשה לגמרי
ניתן לעבוד על נוסחת הנסיגה של $T$ ולקבל נוסחת נסיגה ל- $S$ .

T(n,r)=r(T(n-1,r)+T(n-1,r-1)) \implies S(n,r)r!= r(S(n-1,r)r!+S(n-1,r-1)(r-1)!)

\implies S(n,r)=rS(n-1,r)+S(n-1,r-1)

משפט

הערכים הבאים שווים עבור שלמים אי שליליים $n=k_{1}+k_{2}+\dots+k_{r}$ :

מספר האפשרויות לחלק $n$ כדורים שונים ל- $r$ תאים שונים, כשבתא ה- $i$ יש $k_{i}$ כדורים.
מספר האפשרויות לבחור מקרב $n$ אנשים $r-1$ ועדים שונים וזרים, כשלוועד ה- $i$ נבחרים $k_{i}$ חברים.
מספר האפשרויות לחלק ל- $n$ שונים כדורים מ- $r-1$ סוגים שונים, כשמכל סוג $i$ יש $k_{i}$ כדורים זהים ובכל תא כדור אחד לכל היותר.
מספר המילים באורך $n$ מעל האלפבית $\left\{ 1,2,\dots,r \right\}$ בהן כל אות $i$ מופיעה $k_{i}$ פעמים.
המקדם של המונום $x_{1}^{k_{1}}x_{2}^{k_{2}}\dots x_{r}^{k_{r}}$ בפיתוח המולטינום $(x_{1}+x_{2}+\dots+x_{r})^n$
הערך $\displaystyle\begin{pmatrix}n \\\begin{matrix} k_{1} & k_{2} & \dots & k_{r}\end{matrix}\end{pmatrix}=\frac{n!}{k_{1}!k_{2}!\dots k_{r}!}$

4 - אינדוקציה ורקורסיה

קומבינטוריקה למדעי המחשב

אינדוקציה ורקורסיה

4 - אינדוקציה ורקורסיה

קומבינטוריקה למדעי המחשב

אינדוקציה ורקורסיה

אינדוקציה

אינדוקציה רב מימדית

רקורסיה

בלבול - $Derangement$

נסיגה רב-מימדית

עקרון ההכלה וההדרה

הקדמה

הכלה והדרה

הכלה והדרה עבור שלוש קבוצות

העקרון באופן כללי

בלבול באמצעות הכלה-הדרה

סיכום עד כה

קומבינטוריקה למדעי המחשב

אינדוקציה ורקורסיה

קומבינטוריקה למדעי המחשב

אינדוקציה ורקורסיה

אינדוקציה

אינדוקציה רב מימדית

רקורסיה

בלבול - DerangementDerangementDerangement

נסיגה רב-מימדית

עקרון ההכלה וההדרה

הקדמה

הכלה והדרה

הכלה והדרה עבור שלוש קבוצות

העקרון באופן כללי

בלבול באמצעות הכלה-הדרה

סיכום עד כה

בלבול - $Derangement$