נספח א2 — כלים מתקדמים ויישומים להסתברות

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

★הסיפור של הנספח

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

📋 תזכורת: הכלים והסימונים שבהם נשתמש

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

  1. מה כשיש חפיפה בין מקרים ואי אפשר סתם לחבר? ← הכלה והפרדה
  2. מה הסיכוי שאף אחד לא מקבל את מה ששייך לו? ← בעיית הכובעים (derangements)
  3. מתי משהו חייב לקרות, בלי לחשב? ← שובך יונים
  4. איך סופרים מסלולים בלי לרשום אותם? ← מסלולי סריג, ומה זה אומר ל-ML
  5. איך הופכים ספירה להסתברות (ידי פוקר, בחירה בלי החזרה, בינומי)? ← ספירה לשם הסתברות
  6. כמה גדולים המספרים האלה? ← קצב גדילה, סטירלינג, אנטרופיה
  7. איפה כל זה חי ב-ML? ← "גן החיות" של ספירה ב-ML
🎯 כלי חדש בנספח הזה: אין (כמעט)

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

1הכלה והפרדה

❓ כמה מספרים בין 1 ל-60 מתחלקים ב-2, או ב-3, או ב-5?

נלך בשלבים: (1) שני מאורעות, ריענון, (2) שלושה: למה הנוסחה כזו, (3) הנוסחה הכללית ולמה היא נכונה, (4) מעבדה, (5) "אף אחד" והקשר ל-$\varphi$, (6) גרסת ההסתברות, (7) פונקציות על.

שלב 1: ריענון, שני מאורעות

מספרים עד 60 שמתחלקים ב-2 או ב-3: $|A|=30$ (מתחלקים ב-2), $|B|=20$ (ב-3). אם נחבר $30+20=50$ נספור פעמיים את אלה שמתחלקים בשניהם (כלומר ב-6): $\lfloor60/6\rfloor=10$. לכן $|A\cup B|=30+20-10=40$.

שלב 2: שלושה מאורעות, וניחוש

עכשיו נוסיף $C$ = "מתחלקים ב-5": $|C|=12$. ננסה: $|A|+|B|+|C|=62$. כמובן ספרנו יותר מדי. נחסיר את הזוגות: $|A\cap B|=10$ (ב-6), $|A\cap C|=6$ (ב-10), $|B\cap C|=4$ (ב-15): $62-20=42$. אבל עכשיו פספסנו! המספרים שמתחלקים בשלושתם (ב-30: אלה 30 ו-60, כלומר $|A\cap B\cap C|=2$) נספרו 3 פעמים בסכום הראשון, ואז הוחסרו 3 פעמים בזוגות, לכן "נעלמו". צריך להוסיף אותם בחזרה: $42+2=44$.

💡 אינטואיציה: ספירה בלי ספירה כפולה

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

איבר שנמצא ב...בסכום היחידים $\sum|A_i|$בסכום הזוגות $\sum|A_i\cap A_j|$בשלשה $|A\cap B\cap C|$נטו
קבוצה אחת בלבד+1001
שתי קבוצות בדיוק+2−101
שלוש הקבוצות+3−3+11

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

שלב 3: הנוסחה הכללית ולמה היא נכונה

$$\Big|\bigcup_{i=1}^nA_i\Big|=\sum_i|A_i|-\sum_{i<j}|A_i\cap A_j|+\sum_{i<j<k}|A_i\cap A_j\cap A_k|-\cdots+(-1)^{n+1}|A_1\cap\cdots\cap A_n|.$$

(הסימון $\sum_{i<j}$ פירושו "סכום על כל הזוגות $i<j$", והסימן מתחלף בכל שלב.)

📐 למה זה נכון (הוכחה קצרה)

נבדוק איבר שנמצא ב-$m\ge1$ קבוצות. בסכום היחידים הוא נספר $\binom m1$ פעמים, בסכום הזוגות $\binom m2$ פעמים (כל זוג מתוך הקבוצות ש"שלו"), בשלשות $\binom m3$, וכן הלאה. הנטו:

$$\binom m1-\binom m2+\binom m3-\cdots\pm\binom mm=1.$$

ולמה זה 1? ממשפט הבינום (בתזכורת למעלה) עם $a=-1$ ו-$b=1$: $(-1+1)^m=0$, כלומר $\sum_{j=0}^m(-1)^j\binom mj=0$, כלומר $\binom m0-\binom m1+\binom m2-\cdots=0$, ולכן $\binom m1-\binom m2+\cdots=\binom m0=1$. ∎

שלב 4: מעבדה

🧮 הכלה והפרדה על התחלקות
נסה: N=100 עם 2,3,7: אמור לצאת 72. אחר כך שנה ל-4, 6, 10 (חלוקים לא זרים: החיתוך של "מתחלק ב-4" ו"ב-6" הוא "מתחלק ב-12", לא ב-24).

שלב 5: "אף אחד", והמשלים

לרוב השאלה היא "כמה לא מתחלקים באף אחד?". זה פשוט $N-|\bigcup A_i|$. בדוגמה: $60-44=16$. זה בדיוק מספר המספרים עד 60 שזרים ל-60: פונקציית אוילר $\varphi(60)=16$. הצורה הזו נותנת גם נוסחה ידועה: $\varphi(60)=60\left(1-\tfrac12\right)\left(1-\tfrac13\right)\left(1-\tfrac15\right)=16$, כי הכפל פותח את אותה הכלה והפרדה.

שלב 6: גרסת ההסתברות

אותה נוסחה, עם $P$ במקום $|\cdot|$: $P(A\cup B\cup C)=P(A)+P(B)+P(C)-P(A\cap B)-P(A\cap C)-P(B\cap C)+P(A\cap B\cap C)$.

🎯 טריק: כשהכל סימטרי

אם כל $k$ המאורעות "שווים" (כל חיתוך של $k$ מהם בעל אותה הסתברות $p_k$), הנוסחה מתכנסת ל-$\sum_{k=1}^n(-1)^{k+1}\binom nkp_k$. כי יש $\binom nk$ חיתוכים של $k$ מאורעות. זה בדיוק מה שנעשה בבעיית הכובעים (סעיף 2).

שלב 7: פונקציות על (surjections), והקשר ל-ML

כמה דרכים יש לשייך 5 נקודות מובחנות ל-3 אשכולות (clusters), כך שכל אשכול מקבל לפחות נקודה אחת? הכל: $3^5=243$. נחסר את אלה שבהם אשכול מסוים ריק. תהי $A_i$ = "אשכול $i$ ריק": $|A_i|=2^5$ (הנקודות בוחרות מבין שני האחרים), $|A_i\cap A_j|=1^5$, $|A_1\cap A_2\cap A_3|=0$. לפי הכלה והפרדה:

$$3^5-\left[3\cdot2^5-3\cdot1^5+0\right]=243-93=150.$$

בכלליות: $\sum_{j=0}^k(-1)^j\binom kj(k-j)^n$. ב-ML: זה מספר השיוכים האפשריים של $n$ דגימות ל-$k$ אשכולות ללא אשכול ריק, שחשוב להבין כשמאתחלים k-means. והסיכוי ששיוך אקראי לא משאיר אשכול ריק: $150/243\approx0.617$.

תרגול לסעיף 1

תרגיל 1.1 הכלה והפרדה לשלוש קבוצות ⭐
ב-100 סטודנטים: 60 לומדים מדעי המחשב, 50 מתמטיקה, 40 פיזיקה. 30 לומדים מ"ח ומתמטיקה, 20 מ"ח ופיזיקה, 15 מתמטיקה ופיזיקה, ו-10 לומדים את שלושתם. כמה לא לומדים אף אחד מהשלושה?

פתרון

איחוד: $60+50+40-(30+20+15)+10=95$. לכן $100-95=5$ לא לומדים אף אחד.

תרגיל 1.2 גרסת ההסתברות ⭐⭐
$P(A)=0.5$, $P(B)=0.4$, $P(C)=0.3$; $P(A\cap B)=0.2$, $P(A\cap C)=0.15$, $P(B\cap C)=0.1$; $P(A\cap B\cap C)=0.05$. מה $P(A\cup B\cup C)$, ומה הסיכוי שאף אחד לא קרה?

פתרון

$1.2-0.45+0.05=0.8$. אף אחד: $0.2$.

תרגיל 1.3 מציאת טעות בנוסחה ⭐⭐
תלמיד כותב: $P(A\cup B\cup C)=P(A)+P(B)+P(C)-P(A\cap B)-P(A\cap C)-P(B\cap C)$ (שכח את השלשה). הראה בדוגמה קטנה שהנוסחה שגויה.

פתרון

נקח $A=B=C$ עם $P=0.5$. האיחוד הוא $A$ עצמו: $0.5$. הנוסחה של התלמיד נותנת $1.5-1.5=0$, שגוי. עם השלשה: $1.5-1.5+0.5=0.5$ ✔.

תרגיל 1.4 הכלה והפרדה + משלים ⭐⭐
כמה מספרים בין 1 ל-100 אינם מתחלקים ב-2, ב-3 ולא ב-7?

פתרון

$|A|=50,\ |B|=33,\ |C|=14$; זוגות (6, 14, 21): $16,\ 7,\ 4$; שלשה (42): $2$. איחוד: $97-27+2=72$. אף אחד: $100-72=28$.

תרגיל 1.5 פונקציות על + הסתברות ⭐⭐⭐
4 דגימות משויכות באקראי ובאחידות ל-3 אשכולות. מה הסיכוי שכל האשכולות לא ריקים?

פתרון

כל השיוכים: $3^4=81$. על: $3^4-3\cdot2^4+3\cdot1^4=81-48+3=36$. הסיכוי: $\frac{36}{81}=\frac49\approx0.444$.

🔗 איפה אנחנו בסיפור

הכלה והפרדה מתחילה לשרת אותנו בבעיה מפורסמת: מה הסיכוי שאף אחד לא מקבל את מה ששייך לו?

2בעיית הכובעים (derangements)

❓ $n$ אנשים זורקים את הכובעים שלהם לערימה, וכל אחד מוציא כובע אקראי. מה הסיכוי שאף אחד לא קיבל את הכובע שלו?

נלך בשלבים: (1) מקרים קטנים, (2) הנוסחה בעזרת הכלה והפרדה, (3) התוצאה המפתיעה, (4) הרחבות.

שלב 1: מקרים קטנים

סידור ללא נקודת קבע נקרא derangement, ומספרם מסומן $D_n$. מצאנו $D_1=0$, $D_2=1$, $D_3=2$.

שלב 2: הנוסחה בעזרת הכלה והפרדה

נגדיר $A_i$ = "אדם $i$ קיבל את הכובע שלו". אנחנו רוצים את מספר הסידורים שאינם באף $A_i$, כלומר $n!-|\bigcup A_i|$.

לפי הטריק הסימטרי (שלב 6 בסעיף 1):

$$\Big|\bigcup A_i\Big|=\sum_{k=1}^n(-1)^{k+1}\binom nk(n-k)!=\sum_{k=1}^n(-1)^{k+1}\frac{n!}{k!},$$

כי $\binom nk(n-k)!=\frac{n!}{k!\,(n-k)!}(n-k)!=\frac{n!}{k!}$. לכן:

$$D_n=n!-\Big|\bigcup A_i\Big|=n!\sum_{k=0}^n\frac{(-1)^k}{k!}\ ,\qquad P(\text{אף אחד})=\frac{D_n}{n!}=\sum_{k=0}^n\frac{(-1)^k}{k!}=1-1+\frac1{2!}-\frac1{3!}+\cdots$$

שלב 3: התוצאה המפתיעה

🎩 ערימת הכובעים
💡 מה רואים?

הסיכוי כמעט לא תלוי ב-$n$! כבר מ-$n=5$ הוא בערך 0.3667, ועם עוד אנשים הוא מתכנס ל-$0.36788\ldots$. מספר זה הוא $1/e$ (כאשר $e\approx2.718$ הוא הקבוע המתמטי הידוע), כי הסכום הוא תחילת הטור של $e^{-1}$. (ההוכחה דורשת את פיתוח טיילור של $e^x$, שלא נעסוק בו כאן; את הערך אפשר לבדוק מספרית בטבלה.) המסקנה: בין 5 אנשים או חמישה מיליון, ההסתברות שאף אחד לא יקבל את הכובע שלו היא כ-37%. כל אחד בנפרד מקבל את שלו בסיכוי קטן ($1/n$), אבל יש הרבה אנשים, ושני האפקטים מתקזזים כמעט בדיוק.

שלב 4: הרחבות

➕ נוסחת נסיגה: $D_n=(n-1)(D_{n-1}+D_{n-2})$

אדם 1 מקבל כובע של אדם $j\ne1$ ($n-1$ בחירות). שני מקרים: (א) אדם $j$ מקבל את הכובע של 1 (החלפה), ושאר $n-2$ בלי נקודת קבע: $D_{n-2}$. (ב) אדם $j$ לא מקבל את הכובע של 1: אפשר לחשוב על הכובע של 1 כ"כובע של $j$", ואז יש $n-1$ אנשים ללא נקודת קבע: $D_{n-1}$. לכן $D_n=(n-1)(D_{n-2}+D_{n-1})$. (זה מה שהמעבדה משתמשת בו.)

🔭 הצצה: מספר נקודות הקבע הממוצע הוא בדיוק 1

לכל אדם הסיכוי לקבל את שלו הוא $1/n$, ויש $n$ אנשים. בתורת ההסתברות מוכיחים (בעזרת מושג ה"תוחלת", כלומר הממוצע לטווח ארוך) שהמספר הממוצע של "נקודות קבע" הוא $n\cdot\frac1n=1$, לכל $n$, למרות שלעיתים קרובות (37%) מספרן 0 (ולעיתים 2 או יותר). זה דוגמה ליעילות של "שיטת האינדיקטורים".

🤖 קשר ל-ML

ערבוב אקראי של דוגמאות או תוויות הוא תמורה אקראית. כשמשווים מודל ל"baseline אקראי" (נניח, שיוך תוויות באקראי), כדאי לדעת שתמורה אקראית משאירה בממוצע בדיוק פריט אחד במקומו, ושב-37% מהמקרים אף אחד לא נשאר במקומו. גם "Secret Santa" ו"מבחני פרמוטציה" בנויים על אותה מתמטיקה.

תרגול לסעיף 2

תרגיל 2.1 ספירה ישירה ⭐
רשום את כל ה-derangements של $\{1,2,3,4\}$ שמתחילים ב-2 ("אדם 1 מקבל את הכובע של 2"), וספור. מה $D_4$?

פתרון

שלושה: $(2,1,4,3)$, $(2,3,4,1)$, $(2,4,1,3)$. מכיוון שהסימטריה מתאימה לכל אחד מ-3 הכובעים האפשריים של אדם 1: $D_4=3\cdot3=9$ ✔ (נוסחת הנסיגה: $3\cdot(D_3+D_2)=3\cdot3=9$).

תרגיל 2.2 הפעלת הנוסחה ⭐
חשב את $P(\text{אף אחד})$ עבור $n=5$ בעזרת $\sum_{k=0}^5\frac{(-1)^k}{k!}$.

פתרון

$1-1+\frac12-\frac16+\frac1{24}-\frac1{120}=\frac{44}{120}\approx0.3667$ ($D_5=44$).

תרגיל 2.3 בחר ואז שבץ ⭐⭐
5 אנשים מקבלים כובעים באקראי. מה הסיכוי שבדיוק שניים קיבלו את שלהם?

פתרון

בוחרים את השניים: $\binom52=10$. השלושה האחרים בלי נקודת קבע: $D_3=2$. סה"כ $20$ מתוך $120$: $\frac16$.

תרגיל 2.4 קוד ⭐⭐
דמה "Secret Santa" ל-10 אנשים: ערבב אקראית את range(10) ובדוק באיזה חלק מהמקרים אין נקודת קבע. השווה ל-$\sum_{k=0}^{10}\frac{(-1)^k}{k!}\approx0.36788$.

פתרון
import numpy as np
from math import factorial

rng = np.random.default_rng(0)
n, T = 10, 200_000
hits = sum(not np.any(rng.permutation(n) == np.arange(n)) for _ in range(T))
exact = sum((-1)**k / factorial(k) for k in range(n + 1))
print(hits / T, exact)    # both ~ 0.3679
🔗 איפה אנחנו בסיפור

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

3שובך יונים

❓ בקבוצה של 13 אנשים, האם בהכרח יש שניים שנולדו באותו חודש?

שלב 1: העיקרון

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

אם מכניסים $m$ יונים ל-$n$ שובכים ו-$m>n$, בשובך אחד לפחות יש שתי יונים או יותר. בגרסה המדויקת: יש שובך עם לפחות $\lceil m/n\rceil$ יונים.

💡 אינטואיציה: "קיום בלי בנייה"

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

שלב 2: מה החלק הקשה? לזהות "יונים" ו"שובכים"

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

בחר 6 מספרים כלשהם מ-$\{1,\dots,10\}$. הראה ששניים מהם סכומם 11. השובכים: הזוגות $\{1,10\},\{2,9\},\{3,8\},\{4,7\},\{5,6\}$ (חמישה שובכים, כל אחד סכומו 11). היונים: 6 המספרים שנבחרו, כל אחד נכנס לשובך שלו. 6 יונים ב-5 שובכים: שני מספרים באותו שובך, ובדיוק בזוג כזה סכומם 11. ∎

שלב 3: דוגמה קלאסית ועמוקה יותר

לכל $n$ מספרים שלמים יש רצף עוקב שסכומו מתחלק ב-$n$. הוכחה: יהיו $a_1,\dots,a_n$. נגדיר סכומים חלקיים $S_0=0$, $S_1=a_1$, $S_2=a_1+a_2$, ..., $S_n$. אלה $n+1$ מספרים (יונים). נסתכל על השארית של כל אחד בחלוקה ב-$n$: יש רק $n$ שאריות אפשריות (שובכים). לכן שניים, $S_i$ ו-$S_j$ ($i<j$), בעלי אותה שארית, ולכן $S_j-S_i=a_{i+1}+\cdots+a_j$ מתחלק ב-$n$. ∎

שלב 4: הקשר להסתברות

שובך יונים עוסק ב"בהכרח" (הסתברות 1), בעוד שההסתברות עוסקת במה שביניהם. דוגמה, יום ההולדת: כמה אנשים צריך כדי שלשניים מהם יהיה יום הולדת באותו יום (365 ימים בשנה, כל יום שווה-סיכוי)? שובך יונים מבטיח התאמה רק ב-366 אנשים. אבל החישוב ההסתברותי (בעזרת משלים וכלל הכפל: $1-\frac{365\cdot364\cdots(365-n+1)}{365^n}$) מראה שכבר ב-23 אנשים הסיכוי להתאמה הוא 50.7%. ההסתברות מספרת מה קורה לפני שהוודאות מגיעה.

🤖 קשר ל-ML ולמדעי המחשב

תרגול לסעיף 3

תרגיל 3.1 שובך יונים ישיר ⭐
כמה אנשים צריך כדי להבטיח ששלושה מהם נולדו באותו חודש?

פתרון

נשתמש בגרסה המדויקת: $\lceil m/12\rceil\ge3$ כאשר $m\ge25$. כלומר 25 אנשים (ב-24 אפשר שכל חודש בדיוק פעמיים).

תרגיל 3.2 בחירת שובכים ⭐⭐
5 נקודות נבחרות בריבוע $2\times2$. הוכח ששתיים מהן במרחק של לכל היותר $\sqrt2$.

פתרון

נחלק את הריבוע לארבעה ריבועי יחידה (שובכים). 5 נקודות: שתיים באותו ריבוע יחידה. אלכסון של ריבוע יחידה הוא $\sqrt2$, ולכן המרחק בין שתי נקודות בתוכו לכל היותר $\sqrt2$. ∎

תרגיל 3.3 סכומים חלקיים (אתגר) ⭐⭐⭐
הראה שבין כל 7 מספרים שלמים יש רצף עוקב לא ריק שסכומו מתחלק ב-7. השתמש בשיטה של שלב 3, והדגם על 4, 8, 11, 3, 5, 9, 10.

פתרון

סכומים חלקיים: $0,4,12,23,26,31,40,50$. שאריות מודולו 7: $0,4,5,2,5,3,5,1$. שארית 5 מופיעה שלוש פעמים ($S_2=12$, $S_4=26$, $S_6=40$). ניקח את הראשונים: $S_4-S_2=26-12=14=a_3+a_4=11+3$, וזה מתחלק ב-7 ✔.

תרגיל 3.4 ML: דחיסה ⭐⭐
למה אין אלגוריתם דחיסה ללא אובדן שמקצר כל קובץ בן 1,000 ביטים?

פתרון

קבצים באורך בדיוק 1,000: $2^{1000}$. קבצים קצרים יותר (אורך 0 עד 999): $2^{1000}-1$. אם כל קובץ היה מקוצר, היינו ממפים $2^{1000}$ "יונים" ל-$2^{1000}-1$ "שובכים", ושניים היו מתנגשים ולא היה אפשר לשחזר אותם בדיוק. ∎

🔗 איפה אנחנו בסיפור

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

4מסלולי סריג

❓ אני בפינה השמאלית-תחתונה של רשת $4\times4$ ורוצה להגיע לפינה הימנית-עליונה, כשמותר לזוז רק ימינה או למעלה. כמה מסלולים?

שלב 1: הרעיון, "בחר מקומות"

כל מסלול הוא רצף של 8 צעדים: 4 צעדים ימינה (R) ו-4 צעדים למעלה (U). מסלול נקבע לחלוטין על ידי באילו 4 מקומות מתוך 8 עומדים ה-R (השאר הם U). זה הטריק "בחר מקומות" (מופיע בתזכורת למעלה):

$$\binom84=70.$$
📐 הנוסחה הכללית

מספר המסלולים מהפינה $(0,0)$ ל-$(a,b)$, כשכל צעד הוא ימינה או למעלה, הוא:

$$\binom{a+b}{a}=\binom{a+b}{b}=\frac{(a+b)!}{a!\,b!}.$$

הנימוק: יש $a+b$ צעדים בסך הכל, מהם $a$ ימינה. בוחרים באילו $a$ מקומות (מתוך $a+b$) עומדים צעדי ה-"ימינה".

🧭 מסלולים ברשת

שלב 2: הקשר למשולש פסקל

כדי להגיע לנקודה $(i,j)$, האחרון בצעד בא משמאל (מ-$(i-1,j)$) או מלמטה (מ-$(i,j-1)$). לפי כלל החיבור:

$$\text{paths}(i,j)=\text{paths}(i-1,j)+\text{paths}(i,j-1).$$

זה בדיוק כלל פסקל! ברשת, המספרים ליד כל נקודה יוצרים את משולש פסקל ה"מסובב". וגם בכיוון ההפוך: "שני הסיפורים" (ספירה ישירה ונסיגה) מסכימים.

שלב 3: מסלולים דרך נקודה, ומסלולים שנמנעים מנקודה

שלב 4: הקשר להליכה אקראית

רצף של $n$ הטלות מטבע הוא מסלול: עץ = צעד ימינה, פלי = צעד למעלה. מספר הרצפים עם $k$ עצים הוא $\binom nk$, ולכן מספר המסלולים שמגיעים לנקודה מסוימת בסוף הוא $\binom nk$. זה מקבל משמעות מלאה בהליכה אקראית ובשרשראות מרקוב (תהליכים שבהם כל צעד תלוי רק במצב הנוכחי).

🤖 קשר ל-ML: ספירת מסלולים בלי לרשום אותם

בכלל פסקל יש רעיון מרכזי של תכנות דינמי: במקום לספור (או לרשום) מיליוני מסלולים, מחשבים לכל נקודה את מספר המסלולים אליה מתוך אלה של שכניה. אותו עיקרון מניע אלגוריתמים ב-ML שסוכמים על "המון מסלולים אפשריים": אלגוריתם Forward של HMM וכן Viterbi מחשבים סכום או מקסימום מעל $k^T$ רצפי מצבים מוסתרים בזמן $O(Tk^2)$, בדיוק כמו כלל פסקל.

תרגול לסעיף 4

תרגיל 4.1 בחר מקומות ⭐
כמה מסלולים בין $(0,0)$ ל-$(5,3)$ בצעדי ימינה/למעלה?

פתרון

8 צעדים, מהם 5 ימינה: $\binom85=\binom83=56$.

תרגיל 4.2 מסלולים דרך נקודה ⭐⭐
ברשת $5\times5$, כמה מסלולים מ-$(0,0)$ ל-$(5,5)$ עוברים דרך $(2,3)$?

פתרון

$(0,0)\to(2,3)$: $\binom52=10$. $(2,3)\to(5,5)$: 3 ימינה ו-2 למעלה: $\binom53=10$. סה"כ $10\cdot10=100$.

תרגיל 4.3 מסלולים שנמנעים ⭐⭐
ברשת $3\times3$, כמה מסלולים מ-$(0,0)$ ל-$(3,3)$ לא עוברים דרך $(1,1)$?

פתרון

הכל: $\binom63=20$. דרך $(1,1)$: $\binom21\cdot\binom42=2\cdot6=12$. נמנעים: $20-12=8$.

תרגיל 4.4 הליכה אקראית ⭐⭐
מטילים מטבע הוגן 10 פעמים (עץ = +1, פלי = −1). מה הסיכוי שאחרי 10 צעדים הסכום הוא בדיוק +4?

רמז

סכום +4 אומר $h-t=4$ ו-$h+t=10$. כמה עצים?

פתרון

$h=7$, $t=3$. מספר הרצפים: $\binom{10}7=120$ מתוך $2^{10}=1024$. הסיכוי: $\frac{120}{1024}\approx0.117$.

🔗 איפה אנחנו בסיפור

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

5ספירה לשם הסתברות

❓ בכל בעיית הסתברות עם תוצאות שוות-סיכוי, הדרך היא $P=\frac{|A|}{|\Omega|}$. מה צריך להיזהר ממנו, ואיך נראית התפלגות מבחירה בלי החזרה?

נלך בשלבים: (0) כללי ברזל, (1) בחירה בלי החזרה (היפרגאומטרית), (2) "בונים אובייקט בשדות" (ידי פוקר), (3) כדורים בתאים, (4) בינומי מספירה.

שלב 0: כללי ברזל

⚠️ שני כללים לפני שמתחילים
  1. $\Omega$ במונה ובמכנה חייב להיות אותו מרחב. אם ספרת במכנה "עם סדר", ספור "עם סדר" גם במונה. דוגמה: שני אסים בשני קלפים: עם סדר $\frac{4\cdot3}{52\cdot51}$; בלי סדר $\frac{\binom42}{\binom{52}2}$. שניהם $\frac1{221}$. ערבוב בין השניים נותן שטויות.
  2. התוצאות חייבות להיות שוות-סיכוי. כשמוציאים קלפים בלי החזרה, כל קבוצה של קלפים שווה-סיכוי (וגם כל רצף). אבל כשבוחרים עם חזרות (קוביות, כדורים בתאים) ה"קבוצות עם חזרות" (multisets) לא שוות-סיכוי. למשל בהטלת שתי קוביות יש 21 "זוגות ללא סדר", אבל הזוג $\{1,2\}$ יכול לקרות בשתי דרכים ($(1,2)$ או $(2,1)$) והזוג $\{1,1\}$ בדרך אחת, ולכן הם לא שוות-סיכוי. אז סופרים רצפים ולא ספירות.

שלב 1: בחירה בלי החזרה: התפלגות היפרגאומטרית

בחפיסה של $N$ פריטים, $K$ מהם "מיוחדים" (למשל 13 לבבות מתוך 52). שולפים $n$ בלי החזרה. מה הסיכוי לבדיוק $k$ מיוחדים?

$$P(\text{בדיוק }k)=\frac{\binom Kk\binom{N-K}{n-k}}{\binom Nn}.$$

דוגמה: 5 קלפים, בדיוק 2 לבבות: $\frac{\binom{13}2\binom{39}3}{\binom{52}5}=\frac{78\cdot9139}{2598960}=\frac{712842}{2598960}\approx0.274$. הנרמול ($\sum_kP(k)=1$) נובע מזהות ונדרמונד: ספירת כל הבחירות לפי מספר האדומים $j$ שנבחרו נותנת $\sum_j\binom Kj\binom{N-K}{n-j}=\binom Nn$, כלומר מונים שמסתכמים בדיוק למכנה.

🃏 התפלגות היפרגאומטרית
נסה: N=52, K=13, n=5 (ידי פוקר). אחר כך N=100, K=50, n=10: ההתפלגות הופכת סימטרית וצרה. אחר כך N=20, K=10, n=10: ראה שגם ההסתברות לקבל כולם אדומים קטנה מאוד.

שלב 2: "בונים את האובייקט בשדות", ידי פוקר

כדי לספור ידיים מסוג מסוים, נבנה יד "כמו טופס": כל שדה הוא בחירה, ומכפילים. דוגמה, זוג אחד (שני קלפים באותו ערך ושלושה קלפים אחרים בערכים שונים זה מזה ומהזוג):

  1. ערך הזוג: $13$ אפשרויות.
  2. שני הסוגים של הזוג: $\binom42=6$.
  3. שלושת הערכים האחרים: $\binom{12}3=220$ (בלי סדר, ושונים זה מזה).
  4. הסוג של כל אחד מהשלושה: $4^3=64$.

סה"כ $13\cdot6\cdot220\cdot64=1{,}098{,}240$, ולכן $P=\frac{1098240}{2598960}\approx0.4226$.

ידספירהמספר ידייםהסתברות
זוג אחד$13\cdot\binom42\cdot\binom{12}3\cdot4^3$1,098,2400.4226
שני זוגות$\binom{13}2\binom42^2\cdot44$123,5520.0475
שלישייה$13\cdot\binom43\cdot\binom{12}2\cdot4^2$54,9120.0211
פול האוס$13\cdot\binom43\cdot12\cdot\binom42$3,7440.00144
רביעייה$13\cdot48$6240.00024
⚠️ המלכודת: ספירה כפולה

"בחר זוג ($13\cdot6=78$), ואז כל שלושה קלפים מתוך 50 הנותרים": $78\cdot\binom{50}3=1{,}528{,}800$. יותר מהנכון ($1{,}098{,}240$)! כי "שלושה מתוך 50" כוללים ידיים עם זוג נוסף (נספרות פעמיים, בכל "איזה זוג בחרתי"), שלישיות ופול האוס. הכלל: בנה כל אובייקט בצורה שבה הוא נקבע בדרך אחת בלבד (קודם הזוג, אחר כך שלושה ערכים שונים).

שלב 3: כדורים בתאים

זורקים $n$ כדורים לתוך $k$ תאים באקראי (כל כדור בוחר תא באחידות ובלתי-תלוי). זה מודל לטבלאות hash. ה"רצפים" (איזה כדור בכל תא) שוות-סיכוי, ויש $k^n$ מהם:

⚠️ אל תשתמש בכוכבים וקווים כאן!

2 כדורים ב-2 תאים: מספר "הספירות" (כוכבים וקווים) הוא 3: $(2,0),(1,1),(0,2)$. אבל הן לא שוות-סיכוי: ברצפים, $(1,1)$ יכול לקרות בשתי דרכים (הכדור הראשון בתא 1 והשני בתא 2, או להפך), לעומת $(2,0)$ בדרך אחת. ההסתברויות האמיתיות: $\frac14,\frac12,\frac14$, ולא $\frac13$ לכל אחת. כוכבים וקווים סופר ספירות, והסתברות דורשת לספור רצפים.

שלב 4: ההתפלגות הבינומית, מספירה

$n$ ניסויים בלתי-תלויים, בכל אחד הצלחה בסיכוי $p$ (וכישלון $q=1-p$). מה הסיכוי לבדיוק $k$ הצלחות?

  1. רצף מסוים עם $k$ הצלחות ו-$n-k$ כישלונות (למשל SSFSF) הסתברותו $p^kq^{n-k}$ (אי-תלות והכפלה). זה אותו ערך לכל רצף עם $k$ הצלחות.
  2. יש $\binom nk$ רצפים כאלה ("בחר מקומות" להצלחות), והם זרים.
  3. לכן:
$$P(\text{בדיוק }k)=\binom nkp^kq^{n-k}.$$
💡 הרצפים כבר לא שוות-סיכוי, אבל זה בסדר

כש-$p\ne\frac12$, רצפים שונים אינם שווי-סיכוי (SSFSF שונה מ-FFFFF). אבל כל הרצפים עם אותו $k$ שווים, ולכן "מספר רצפים × הסתברות כל אחד" עובד. זו הסיבה שהסתברות אינה רק ספירה: היא ספירה משוקללת.

דוגמה: 5 הטלות של מטבע מוטה עם $p=0.3$ לעץ, בדיוק 2 עצים: $\binom52\cdot0.3^2\cdot0.7^3=10\cdot0.09\cdot0.343\approx0.3087$. משפט הבינום מבטיח שהסכום על כל $k$ הוא $(p+q)^n=1$ (כי $p+q=1$).

תרגול לסעיף 5

תרגיל 5.1 היפרגאומטרית ⭐
מחלקים 5 קלפים מחפיסה. מה הסיכוי שיהיו בדיוק 2 לבבות? (בדוק במעבדה.)

פתרון

$\frac{\binom{13}2\binom{39}3}{\binom{52}5}=\frac{712842}{2598960}\approx0.2743$.

תרגיל 5.2 בניית יד בשדות ⭐⭐
מה הסיכוי לפול האוס (שלושה מאותו ערך וזוג מערך אחר) ב-5 קלפים?

פתרון

ערך השלישייה: 13; סוגיה: $\binom43=4$; ערך הזוג: 12; סוגיו: $\binom42=6$. סה"כ $13\cdot4\cdot12\cdot6=3744$, ו-$\frac{3744}{2598960}\approx0.00144$.

תרגיל 5.3 מציאת טעות (ספירה כפולה) ⭐⭐
סטודנט סופר ידיים עם "לפחות אס אחד" כך: "בוחרים אס (4), ואז 4 קלפים מ-51: $4\binom{51}4$". מה הבעיה, ואיך מחשבים נכון?

פתרון

יד עם 2 אסים נספרת פעמיים (איזה אס "בחרתי"), עם 3 אסים שלוש פעמים וכו'. נכון: משלים. ללא אסים: $\binom{48}5$. $P(\text{לפחות אס})=1-\frac{\binom{48}5}{\binom{52}5}=1-\frac{1712304}{2598960}\approx0.341$.

תרגיל 5.4 כדורים בתאים ⭐⭐
3 כדורים נזרקים באקראי ל-5 תאים. מה הסיכוי שכולם בתאים שונים? ומה הסיכוי שתא 1 ריק?

פתרון

שונים: $\frac{5\cdot4\cdot3}{5^3}=\frac{60}{125}=0.48$. תא 1 ריק: $\left(\frac45\right)^3=0.512$.

תרגיל 5.5 בינומי ⭐⭐
מטבע מוטה עם $p=0.3$ לעץ מוטל 5 פעמים. חשב את $P(k)$ לכל $k=0,\dots,5$, ובדוק שהסכום 1.

פתרון

$k=0$: $0.7^5=0.1681$. $k=1$: $5\cdot0.3\cdot0.7^4=0.3602$. $k=2$: $0.3087$. $k=3$: $10\cdot0.3^3\cdot0.7^2=0.1323$. $k=4$: $5\cdot0.3^4\cdot0.7=0.02835$. $k=5$: $0.3^5=0.00243$. סכום: $1$ ✔.

תרגיל 5.6 הכלה והפרדה + היפרגאומטרית (אתגר) ⭐⭐⭐
מה הסיכוי שב-5 קלפים מופיעים כל ארבעת הסוגים?

רמז

$A_i$ = "אין קלף מסוג $i$". חפש את $P(\bigcup A_i)$ בהכלה והפרדה, ואז משלים.

פתרון

$|A_i|=\binom{39}5$, $|A_i\cap A_j|=\binom{26}5$, $|A_i\cap A_j\cap A_k|=\binom{13}5$, ארבעת הסוגים ביחד: 0. $|\bigcup|=4\binom{39}5-6\binom{26}5+4\binom{13}5=2303028-394680+5148=1913496$. לכן $P(\text{כולם})=1-\frac{1913496}{2598960}\approx0.2637$. בדיקה ישירה: סוג אחד מופיע פעמיים ($4\binom{13}2\cdot13^3=685464$), כלומר $0.2637$ ✔.

🔗 איפה אנחנו בסיפור

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

6קצב גדילה: עצרת, סטירלינג ואנטרופיה

❓ כמה גדול $n!$? והאם יש דרך לדעת בערך כמה גדול $\binom{n}{k}$ בלי לחשב?

נלך בשלבים: (1) הדירוג של הגדילה, (2) נוסחת סטירלינג, (3) $\binom nk$ ואנטרופיה, (4) טיפים לחישוב בקוד.

שלב 1: מי מנצח?

$n$$n^2$$2^n$$n!$$n^n$
101001,0243,628,800$10^{10}$
20400$\approx10^6$$2.4\cdot10^{18}$$10^{26}$

סדר הגדילה: פולינום $\ll$ מעריכית $\ll$ עצרת $\ll$ $n^n$. כבר ב-$n=20$ העצרת גדולה פי $10^{12}$ מ-$2^n$.

שלב 2: נוסחת סטירלינג (ללא הוכחה)

$$n!\approx\sqrt{2\pi n}\left(\frac ne\right)^n\ ,\qquad \ln n!\approx n\ln n-n+\tfrac12\ln(2\pi n).$$

הקירוב הופך מדויק יחסית ככל ש-$n$ גדל (השגיאה היחסית בערך $\frac1{12n}$). את ההוכחה נשאיר ללימוד מתקדם יותר, ופה נבדוק מספרית. שים לב שבשימוש הנפוץ ב-ML מספיק הפשוט: $\ln n!\approx n\ln n-n$.

📏 סטירלינג ואנטרופיה

שלב 3: $\binom nk$ ואנטרופיה

ננסה להעריך כמה מחרוזות בינאריות באורך $n$ יש עם בדיוק $qn$ אחדות. נסמן ב-$H(q)$ את האנטרופיה הבינארית:

$$H(q)=-q\log_2q-(1-q)\log_2(1-q)\qquad(\text{ביטים}).$$

אז:

$$\binom n{qn}\approx\frac{2^{\,n\,H(q)}}{\sqrt{2\pi\,n\,q(1-q)}}\ ,\qquad\text{ובקירוב גס: }\binom n{qn}\approx2^{\,n\,H(q)}.$$
💡 אינטואיציה: $H$ הוא "כמה ביטים לשם"

הקירוב אומר שיש בערך $2^{nH(q)}$ מחרוזות כאלה, ולכן כדי "לתת שם" לאחת מהן צריך $\log_2$ של זה $\approx nH(q)$ ביטים, כלומר $H(q)$ ביטים לכל סימן. כש-$q=\frac12$ זה 1 ביט לסימן (אין רמז). ככל ש-$q$ רחוק מ-$\frac12$ (נניח 0.1), יש פחות מחרוזות טיפוסיות וצריך פחות ביטים ($H(0.1)\approx0.47$). זו האנטרופיה (מושג מרכזי בתורת האינפורמציה, ושימושי ב-ML), והיא בעצם ספירה. בהתחלה הייתה קומבינטוריקה.

שלב 4: טיפים לחישוב בקוד

from math import lgamma, log, exp

def log_binom(n, k):
    return lgamma(n + 1) - lgamma(k + 1) - lgamma(n - k + 1)

def binom_pmf(n, k, p):
    return exp(log_binom(n, k) + k * log(p) + (n - k) * log(1 - p))

print(binom_pmf(1000, 500, 0.5))   # ~0.02523 (no overflow!)

תרגול לסעיף 6

תרגיל 6.1 השוואת קצבים ⭐
מי גדול יותר: $20!$ או $2^{60}$?

פתרון

$20!\approx2.43\cdot10^{18}$ ו-$2^{60}\approx1.15\cdot10^{18}$. העצרת גדולה בפי 2 בערך.

תרגיל 6.2 הערכה עם סטירלינג ⭐⭐
כמה ספרות יש ל-$52!$ (מספר הסידורים של חפיסת קלפים)? השתמש ב-$\ln n!\approx n\ln n-n+\frac12\ln(2\pi n)$.

פתרון

$\ln52!\approx52\ln52-52+\tfrac12\ln(2\pi\cdot52)\approx205.46-52+2.89=156.35$. לכן $\log_{10}52!\approx\frac{156.35}{2.3026}=67.9$, כלומר $52!\approx8\cdot10^{67}$ ו-68 ספרות. (הערך האמיתי: $8.07\cdot10^{67}$.) כל חפיסה מעורבת היטב היא כנראה סידור שמעולם לא התרחש.

תרגיל 6.3 $\binom{n}{n/2}$ ⭐⭐
הראה בעזרת הנוסחה של שלב 3 ש-$\binom{n}{n/2}\approx\frac{2^n}{\sqrt{\pi n/2}}$, והעריך את $\binom{1000}{500}/2^{1000}$.

פתרון

$q=\frac12$: $H(\tfrac12)=1$ ו-$2\pi nq(1-q)=\frac{\pi n}2$. לכן $\binom n{n/2}\approx\frac{2^n}{\sqrt{\pi n/2}}$. ל-$n=1000$: $\frac1{\sqrt{500\pi}}\approx0.0252$. כלומר מבין כל $2^{1000}$ מחרוזות, רק כ-2.5% הן עם בדיוק 500 אחדות. (זה הסיכוי ש-1000 הטלות מטבע ייתנו בדיוק 500 עצים.)

תרגיל 6.4 קוד: יציבות נומרית ⭐⭐
למה factorial(1000)/(factorial(500)**2) בפלואט נכשל, ואיך מחשבים את אותו דבר בלוגים?

פתרון

ב-float64 factorial(1000) חורג (גדול ממש מ-$10^{308}$), ולכן התוצאה inf או שגיאה. בלוגים: exp(lgamma(1001) - 2*lgamma(501) - 1000*log(2)) נותן $\binom{1000}{500}/2^{1000}\approx0.02523$ בלי גלישה.

🔗 איפה אנחנו בסיפור

עכשיו אפשר לראות איפה כל המספרים האלה מופיעים ב-ML: "גן החיות" של ספירה.

7גן החיות של ספירה ב-ML

❓ באילו מקומות ב-ML נתקלים בספירה, ומה אנחנו לומדים מגודל המספר?

מה סופריםהנוסחהגודל טיפוסיהמשמעות
תתי-קבוצות של $d$ פיצ'רים$2^d$$d=50$: $\approx10^{15}$בחירת פיצ'רים בכוח גס בלתי-אפשרית
פונקציות בוליאניות על $d$ ביטים$2^{2^d}$$d=4$: 65,536; $d=6$: $1.8\cdot10^{19}$למה חייבים להניח הנחות על המבנה (inductive bias)
תיוגים בינאריים של $n$ נקודות$2^n$$n=20$: מיליוןמושג "ניפוץ" (shattering) ו-VC dimension: מחלקה "מנפצת" $n$ נקודות אם היא מייצרת את כל $2^n$ התיוגים
זוגות דוגמאות$\binom n2$$n=10^6$: $5\cdot10^{11}$למה מטריצות מרחקים לא מתאימות לדאטה גדול
mini-batches בגודל $B$ מתוך $N$$\binom NB$$N=10^4$, $B=32$: $\approx4\cdot10^{92}$למה אין שתי ריצות אימון זהות בלי seed
סדרי ערבוב של $N$ דוגמאות$N!$$N=52$: $8\cdot10^{67}$עוצמת המילה "אקראי"
וקטורי bag-of-words$\binom{n+V-1}{V-1}$$V=10^4$, $n=100$: עצוםההבדל בין רצף לספירה
שיוכים של $n$ נקודות ל-$k$ אשכולות$k^n$; בלי אשכול ריק: surjections (סעיף 1)$n=100$, $k=3$: $5\cdot10^{47}$למה k-means מוצא רק מינימום מקומי
התנגשויות hashשובך יונים / יום ההולדת$\sqrt{k}$ מפתחות מספיקים"בטוח" לעומת "סביר"
סימטריות ברשת עם $h$ יחידות חבויות$h!$$h=64$: $10^{89}$אותו מודל נראה "שונה" אחרי ערבוב יחידות: בעיית זהות בלמידה
💡 הלקח

בשימוש ב-ML כמעט תמיד המספרים האלה עצומים. זו הסיבה שעוזרים לנו שלושה כלים: הסתברות (במקום לספור הכל, מתארים "כמה סביר"), לוגים (במקום להתמודד עם מספרים ענקיים), והנחות מבנה (שמצמצמות את המרחב).

★תרגול משולב

בלי כותרת טכניקה. כל התרגילים משלבים כמה כלים מנספחי א1 ו-א2 (הטכניקה רשומה בפתרון).

תרגיל מ.1 ⭐⭐⭐
5 גברים ו-4 נשים מסתדרים בשורה כך שאין שתי נשים צמודות. כמה סידורים?

רמז

קודם סדר את הגברים. כמה "רווחים" נוצרים ביניהם ובקצוות?

פתרון

טכניקת הרווחים (gaps). סידור 5 הגברים: $5!=120$. נוצרים 6 רווחים (4 בין גברים ו-2 בקצוות). הנשים נכנסות לרווחים שונים (אחרת שתיים יהיו צמודות): בוחרים 4 מתוך 6 רווחים ומסדרים אותן בהם: $\binom64\cdot4!=15\cdot24=360$. סה"כ $120\cdot360=43{,}200$.

תרגיל מ.2 ⭐⭐⭐
מטילים מטבע הוגן 7 פעמים. מה הסיכוי שלא יופיעו שני עצים רצופים?

רמז

אותה טכניקה: קודם הפלים, אחר כך ה"רווחים" שבהם עצים יכולים לשבת. לכל $k$ מספר עצים, כמה פלים יש?

פתרון

רווחים + בחר מקומות. עם $k$ עצים יש $7-k$ פלים, ו-$8-k$ רווחים (בין הפלים ובקצוות). העצים נכנסים לרווחים שונים: $\binom{8-k}k$. סה"כ $\sum_{k=0}^4\binom{8-k}k=1+7+15+10+1=34$ מתוך $2^7=128$: $\frac{34}{128}\approx0.266$.

תרגיל מ.3 ⭐⭐
בכמה דרכים אפשר לבחור 3 מושבים לא סמוכים מתוך 10 מושבים בשורה?

רמז

בחר 3 מושבים, אחר כך "כווץ" את הרווח: אם אסור שיהיו צמודים, הורד 0, 1, 2 מהמספרים המוזמנים.

פתרון

התאמה חח"ע + צירופים. אם המושבים $a<b<c$ לא סמוכים, אז $a<b-1<c-2$ הם שלושה מספרים שונים מתוך $\{1,\dots,8\}$, וההתאמה הפיכה. לכן $\binom83=56$.

תרגיל מ.4 ⭐⭐
בקבוצה של 7 אנשים, כל אחד מקבל באקראי מספר מ-1 עד 10 (חזרות מותרות). מה הסיכוי שכולם שונים? מה הסיכוי שיש חזרה?

פתרון

כדורים בתאים + משלים. שונים: $\frac{10\cdot9\cdot8\cdot7\cdot6\cdot5\cdot4}{10^7}=\frac{604800}{10^7}=0.06048$. חזרה: $1-0.06048\approx0.94$.

8סיכום הנספח

הכלימתיהרעיון
הכלה והפרדהאיחוד של מקרים חופפיםסכום, מינוס זוגות, פלוס שלשות... כך שכל איבר נספר פעם אחת
derangements"אף אחד לא במקום"$D_n=n!\sum\frac{(-1)^k}{k!}$, וההסתברות $\approx\frac1e$ ללא תלות ב-$n$
שובך יונים"בהכרח" / "קיים"הקושי הוא להגדיר שובכים (דוגמה: זוגות סכום 11)
מסלולי סריגרצפים של שני סוגי צעדים$\binom{a+b}a$ ("בחר מקומות"), ונסיגה שהיא כלל פסקל
ספירה לשם הסתברות$P=|A|/|\Omega|$אותו $\Omega$ במונה ובמכנה; בונים אובייקט בשדות; הרצפים (לא הספירות) שוות-סיכוי
היפרגאומטריתבחירה בלי החזרה$\frac{\binom Kk\binom{N-K}{n-k}}{\binom Nn}$
בינומי מספירהניסויים בלתי-תלויים$\binom nkp^kq^{n-k}$: ספירה משוקללת
סטירלינג ואנטרופיההערכת גודל$\ln n!\approx n\ln n-n$; $\binom n{qn}\approx2^{nH(q)}$
🎯 הטיפים החשובים ביותר
← נספח א1 מפת הדרכים →