נספח א1 — יסודות הספירה

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

★למה נספח על ספירה, ואיך משתמשים בו

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

$$P(\text{המאורע})=\frac{\text{מספר התוצאות שמתאימות למאורע}}{\text{מספר כל התוצאות האפשריות}}.$$

למשל הסיכוי לקבל מספר זוגי בקובייה הוא $\frac36$: 3 תוצאות מתאימות (2, 4, 6) מתוך 6. כלומר חצי מההסתברות היא ספירה: צריך לדעת לספור בלי לרשום את כל התוצאות. בידי פוקר, למשל, יש 2,598,960 תוצאות, ואי אפשר לרשום אותן.

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

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

  1. איך סופרים בלי לרשום הכל? ← חיבור, כפל, משלים והתאמה חח"ע
  2. כמה דרכים לסדר פריטים? ← תמורות ועצרת
  3. כמה דרכים לבחור פריטים? ← צירופים, משולש פסקל, משפט הבינום
  4. מה כשיש כמה קבוצות מסומנות? ← מקדם מולטינומי
  5. מה כשמותר לחזור על אותו פריט? ← כוכבים וקווים
  6. איך בוחרים כלי לבעיה חדשה? ← מפת החלטה ותרגול משולב

איפה כל כלי משמש בהסתברות וב-ML

כליהשימוש
כפל ומשליםכמעט כל חישוב הסתברות
צירופים ומשפט הבינוםההתפלגות הבינומית ("כמה הצלחות ב-$n$ ניסיונות") ונרמולה
מקדם מולטינומיההתפלגות המולטינומית וספירות מילים
כוכבים וקוויםbag-of-words, היסטוגרמות, חלוקת "תקציב"
תמורותערבוב דאטה, מבחני פרמוטציה, חישוב $n!$ בלוגים
🎯 המשפט האחד שכדאי לזכור

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

1עקרונות היסוד של הספירה

❓ כמה "דרכים" יש לעשות משהו, כשאי אפשר לרשום אותן אחת-אחת?

נלך בשלבים: (1) כלל החיבור, (2) כלל הכפל, (3) הספירה בחיסור (משלים), (4) התאמה חח"ע, (5) ספירה עם עודף. הסימון $|A|$ פירושו "מספר האיברים בקבוצה $A$".

שלב 1: כלל החיבור ("או")

📐 כלל החיבור

צריך לבחור פריט אחד, והוא יכול להיות מסוג 1 (יש $a_1$ אפשרויות), או מסוג 2 (יש $a_2$ אפשרויות), ... או מסוג $m$ (יש $a_m$ אפשרויות), כשאין פריט ששייך לשני סוגים. אז מספר האפשרויות הכולל הוא:

$$a_1+a_2+\cdots+a_m.$$

דוגמה: לקינוח יש 3 סוגי עוגה או 2 סוגי גלידה: $3+2=5$ אפשרויות. דוגמה נוספת: בכיתה 12 בנים ו-15 בנות, ולבחור נציג אחד (בן או בת): $12+15=27$.

💡 אינטואיציה

שתי קבוצות הן זרות אם אין להן איבר משותף. כשסופרים איחוד של קבוצות זרות, פשוט מחברים את הגדלים: $|A\cup B|=|A|+|B|$. אם יש חפיפה, האיבר המשותף ייספר פעמיים, וצריך להחסיר אותו. זה יהיה "הכלה והפרדה" (בנספח א2).

שלב 2: כלל הכפל ("וגם / אחר כך")

📐 כלל הכפל

תהליך מורכב מ-$m$ שלבים ברצף. בשלב 1 יש $a_1$ אפשרויות, בשלב 2 יש $a_2$, ..., בשלב $m$ יש $a_m$ (המספר בכל שלב לא תלוי במה שנבחר בשלבים הקודמים). אז מספר התהליכים השונים הוא:

$$a_1\cdot a_2\cdot\cdots\cdot a_m.$$

למה? לכל בחירה בשלב 1 יש $a_2$ המשכים, ויש $a_1$ בחירות כאלה: $a_1\cdot a_2$. כך הלאה. תחשוב על עץ שבו כל ענף מתפצל. או על טבלה: 3 חולצות ו-2 מכנסיים נותנים טבלה של 3 שורות ו-2 עמודות, כלומר $3\cdot2=6$ תלבושות.

עוד דוגמאות: קוד PIN בן 4 ספרות: $10\cdot10\cdot10\cdot10=10^4$. מילה בת 3 אותיות מתוך 26, בלי לחזור על אות: $26\cdot25\cdot24=15{,}600$. (הראשונה: 26, השנייה: 25 כי אחת כבר "נלקחה", השלישית: 24.)

⚠️ הדיוק שחשוב

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

🎯 "או" או "וגם"? מה לעשות?

שאל את עצמך: האם אני בוחר אחד מבין כמה מקרים (חיבור) או מבצע כמה בחירות ברצף (כפל)? "עוגה או גלידה" = חיבור. "חולצה וגם מכנס" = כפל. הטעות הנפוצה ביותר בקומבינטוריקה היא להחליף ביניהם.

שלב 3: ספירה בחיסור (משלים)

📐 כלל המשלים
$$\text{מספר המקרים הטובים}=\text{מספר כל המקרים}-\text{מספר המקרים הרעים}.$$

כשקשה לספור ישירות, סופרים את ההפך וחוסרים. דוגמה: כמה קודי PIN בני 4 ספרות יש עם לפחות ספרה חוזרת אחת? ישירות זה מסובך (איזו ספרה? כמה פעמים?). בחיסור: כל הקודים הם $10^4=10{,}000$ (כלל הכפל). "הרעים" הם הקודים בלי חזרות בכלל: $10\cdot9\cdot8\cdot7=5{,}040$. לכן $10{,}000-5{,}040=4{,}960$.

שלב 4: התאמה חח"ע (bijection)

📐 עקרון ההתאמה

אם אפשר להתאים לכל איבר בקבוצה $A$ איבר אחד ויחיד בקבוצה $B$, וכל איבר ב-$B$ מתאים לאיבר אחד ויחיד ב-$A$, אז $|A|=|B|$. (התאמה כזו נקראת חד-חד-ערכית ועל.)

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

💡 אינטואיציה: "אותו מספר, תלבושת אחרת"

כמה תתי-קבוצות יש לקבוצה בת $n$ איברים? לכל איבר מחליטים "בפנים" או "בחוץ", כלומר רצף של $n$ כן/לא. תתי-קבוצות ↔ רצפים בינאריים באורך $n$ (כל מקום: 0 או 1). לרצפים אפשר להפעיל את כלל הכפל: $2\cdot2\cdots2=2^n$. לכן יש $2^n$ תתי-קבוצות.

שלב 5: "ספור עם עודף, וחלק"

📐 העיקרון

אם ספרנו כל פריט (שרצינו לספור) בדיוק $r$ פעמים, אז המספר האמיתי הוא:

$$\text{המספר האמיתי}=\frac{\text{מה שספרנו}}{r}.$$

דוגמה: $n$ אנשים נפגשים, וכל זוג לוחץ יד פעם אחת. כמה לחיצות? נספור "כל אדם לוחץ יד לכל אחד אחר": $n(n-1)$ (לכל אחד מ-$n$ אנשים, $n-1$ אחרים). אבל כל לחיצה נספרה פעמיים (פעם מכל צד). לכן $\frac{n(n-1)}{2}$. ל-$n=10$: $45$.

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

תרגול לסעיף 1

תרגיל 1.1 כפל ⭐
לוחית רישוי בנויה משתי אותיות (מתוך 26) ואחריהן שלוש ספרות. כמה לוחיות יש?

פתרון

$26\cdot26\cdot10\cdot10\cdot10=676{,}000$.

תרגיל 1.2 משלים ⭐⭐
כמה מספרים בין 1 ל-999 מכילים לפחות פעם אחת את הספרה 7?

רמז

ספור את אלה שאינם מכילים 7 כלל. תחשוב על מספרים כרצפים של שלוש ספרות (עם אפסים מובילים).

פתרון

רצפים של שלוש ספרות מ-000 עד 999: $10^3=1000$. בלי 7 בכלל: $9^3=729$. לכן עם 7: $1000-729=271$. (המספר 000 אינו מכיל 7, ולכן ההחסרה נכונה גם לטווח 1–999.)

תרגיל 1.3 התאמה חח"ע ⭐⭐
הראה שלקבוצה בת $n\ge1$ איברים יש בדיוק $2^{n-1}$ תתי-קבוצות בגודל זוגי. (בהמשך: זה מסביר למה בהטלת מטבע הוגן 10 פעמים הסיכוי למספר זוגי של עצים הוא בדיוק חצי.)

רמז

תתי-קבוצות בגודל זוגי ↔ תתי-קבוצות בגודל אי-זוגי: מה קורה אם "הופכים" את האיבר הראשון (מוציאים אם הוא בפנים, מכניסים אם הוא בחוץ)?

פתרון

ההיפוך של איבר 1 משנה את גודל הקבוצה ב-1, ולכן הופך זוגי לאי-זוגי ולהפך. זו התאמה חח"ע בין זוגיות לאי-זוגיות, ולכן הכמויות שוות: כל אחת $2^n/2=2^{n-1}$.

תרגיל 1.4 מציאת טעות ⭐
דני סופר: "בכיתה 12 בנים ו-15 בנות. כמה דרכים לבחור נציג אחד?" ועונה $12\cdot15=180$. מה הטעות, ומה התשובה?

פתרון

"בן או בת" הם מקרים זרים, ולכן מחברים: $12+15=27$ (פשוט כל תלמיד בכיתה). הכפל היה נכון לשאלה אחרת: "כמה זוגות (בן, בת) אפשר ליצור".

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

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

2תמורות: כמה דרכים לסדר?

❓ בכמה דרכים אפשר לסדר 5 אנשים בשורה?

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

שלב 1: עצרת

📐 עצרת ומספר הסידורים

$n$ פריטים שונים זה מזה אפשר לסדר בשורה ב-

$$n!=n\cdot(n-1)\cdot(n-2)\cdots2\cdot1$$

דרכים. הסימון $n!$ נקרא "$n$ עצרת" (factorial). בהגדרה, $0!=1$.

למה? זה כלל הכפל. למקום הראשון יש $n$ מועמדים. אחרי שבחרנו, למקום השני נשארו $n-1$. אחר כך $n-2$, וכך עד המקום האחרון שיש לו מועמד אחד בלבד.

דוגמה: 5 אנשים בשורה: $5!=5\cdot4\cdot3\cdot2\cdot1=120$. (ולמה $0!=1$? יש בדיוק דרך אחת לסדר "אף אחד": לא לעשות כלום.)

💡 אינטואיציה: העצרת מתפוצצת

הערכים הראשונים: $5!=120$, $10!=3{,}628{,}800$, $20!\approx2.4\cdot10^{18}$ (יותר מאלף מיליון מיליון). לכן אי אפשר "לנסות כל סדר" כבר ב-20 פריטים, וכדאי תמיד לחשב עצרות בלוגים או בשברים מצומצמים (פירוט בנספח א2).

שלב 2: סידור חלקי

📐 סידור $k$ מתוך $n$

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

$$n\cdot(n-1)\cdots(n-k+1)=\frac{n!}{(n-k)!}.$$

למה? כלל הכפל, אבל עוצרים אחרי $k$ מקומות: $n$ אפשרויות למקום 1, $n-1$ למקום 2, ..., $n-k+1$ למקום $k$. השוויון לשבר: $n!=n\cdots(n-k+1)\cdot(n-k)!$, ולכן כשמחלקים ב-$(n-k)!$ הזנב $(n-k)\cdots1$ מצטמצם ומה שנשאר הוא המכפלה של $k$ הגורמים הראשונים.

דוגמה: מדליות זהב, כסף וארד לאחד מ-5 רצים ($n=5$, $k=3$): $5\cdot4\cdot3=\frac{5!}{2!}=60$.

שלב 3: הטריק "הדבקה"

📐 פריטים שחייבים להיות צמודים

מסדרים $n$ פריטים שונים בשורה, ו-$m$ מסוימים מהם חייבים להיות צמודים (בכל סדר פנימי ביניהם). מספר הסידורים:

$$(n-m+1)!\cdot m!$$

במקרה הנפוץ של שני פריטים ($m=2$): $2\cdot(n-1)!$. ושני פריטים שהם לא צמודים (בחיסור): $n!-2\cdot(n-1)!$.

למה? מדביקים את $m$ הפריטים ל"בלוק" אחד. עכשיו יש $n-m+1$ "יחידות" (הבלוק, ועוד $n-m$ פריטים בודדים), ואותן מסדרים ב-$(n-m+1)!$ דרכים. בתוך הבלוק אפשר לסדר את $m$ הפריטים ב-$m!$ דרכים. שני השלבים עצמאיים, ולכן מכפילים.

דוגמה: 5 אנשים בשורה, ודנה ורון חייבים לשבת צמודים. $n=5$, $m=2$: $(5-2+1)!\cdot2!=4!\cdot2=24\cdot2=48$. ואם הם לא רוצים לשבת צמודים: $5!-48=120-48=72$.

⚠️ הכפל ב-$m!$ תלוי בשאלה

אם נדרש שדנה תשב משמאל לרון (סדר פנימי קבוע), אין כפל ב-$m!$: התשובה $4!=24$.

שלב 4: אותיות חוזרות

📐 סידור עם פריטים זהים

יש $n$ פריטים, מהם $m_1$ מסוג 1 (הזהים זה לזה), $m_2$ מסוג 2, ..., $m_r$ מסוג $r$, כאשר $m_1+m_2+\cdots+m_r=n$. מספר הסידורים השונים בשורה:

$$\frac{n!}{m_1!\cdot m_2!\cdots m_r!}.$$

למה? "ספור עם עודף, וחלק". דמיין שכל הפריטים שונים (נצבע אותם בצבעים שונים): יש $n!$ סידורים. אבל אחר כך "מוחקים את הצבעים". סידור אמיתי אחד (למשל BANANA) מופיע הרבה פעמים ברשימת $n!$: אפשר להחליף ביניהן את שלוש ה-A ב-$3!$ דרכים, ואת שתי ה-N ב-$2!$ דרכים (וה-B ב-$1!$). כלומר כל סידור אמיתי נספר בדיוק $m_1!\cdot m_2!\cdots m_r!$ פעמים (אותו מספר לכולם). לכן מחלקים בו.

דוגמה: כמה "מילים" שונות אפשר ליצור מסידור האותיות של BANANA? $n=6$, ו-$m_A=3$, $m_N=2$, $m_B=1$:

$$\frac{6!}{3!\cdot2!\cdot1!}=\frac{720}{6\cdot2\cdot1}=60.$$

נסה בעצמך:

🔤 מחשבון אנגרמות
נסה: BANANA (60). AAB (3, ותראה את כולן ברשימה). ABCD (24, כל האותיות שונות). AAAA (1).

שלב 5: שולחן עגול

📐 סידור סביב שולחן עגול

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

$$\frac{n!}{n}=(n-1)!.$$

למה? "ספור עם עודף וחלק": בשורה יש $n!$ סידורים. כל סידור עגול אחד מופיע שם $n$ פעמים (אחת לכל אחד מ-$n$ הסיבובים האפשריים), לכן $\frac{n!}{n}=(n-1)!$. דרך נוספת לראות: "קבע" אדם אחד במקומו, כדי שלא יהיו סיבובים. השאר מסתדרים ב-$(n-1)!$ דרכים.

דוגמה: 5 אנשים סביב שולחן: $4!=24$. ואם שניים מהם חייבים לשבת צמודים: הם בלוק, ויש 4 "יחידות" סביב השולחן: $(4-1)!=6$, ובבלוק $2!$ סדרים: $6\cdot2=12$.

🤖 קשר ל-ML

ערבוב דאטה לפני אימון (shuffle) הוא בחירה של אחת מתוך $N!$ תמורות. כל פעם שמוסיפים random seed, בעצם מציינים איזו תמורה בוחרים. מבחני פרמוטציה (permutation tests) בודקים אם תוצאה יכולה להיות מקרית על ידי ערבוב התוויות הרבה פעמים, ותלויים בכך שמספר התמורות עצום.

תרגול לסעיף 2

תרגיל 2.1 עצרת ⭐
7 ספרים שונים על מדף. בכמה דרכים אפשר לסדר אותם? ואם רק 3 מהם נבחרים ומסודרים?

פתרון

$7!=5040$. סידור חלקי של 3 מתוך 7: $7\cdot6\cdot5=210$.

תרגיל 2.2 הדבקה + משלים ⭐⭐
6 אנשים בשורה. שניים מסוימים לא רוצים לשבת צמודים. כמה סידורים?

פתרון

הכל: $6!=720$. צמודים: בלוק, 5 יחידות ושני סדרים: $5!\cdot2=240$. לא צמודים: $720-240=480$.

תרגיל 2.3 אותיות חוזרות ⭐⭐
כמה מילים שונות אפשר ליצור מ-STATISTICS?

רמז

ספור את האותיות: S ×3, T ×3, A ×1, I ×2, C ×1. סה"כ 10.

פתרון

$\frac{10!}{3!\,3!\,1!\,2!\,1!}=\frac{3628800}{72}=50{,}400$. (בדוק במחשבון למעלה.)

תרגיל 2.4 שולחן עגול + הדבקה ⭐⭐
4 זוגות נשואים מתיישבים סביב שולחן עגול, וכל זוג יושב צמוד. כמה סידורים?

פתרון

כל זוג הוא בלוק: 4 בלוקים סביב שולחן עגול: $(4-1)!=6$. בכל בלוק שני סדרים פנימיים: $2^4=16$. סה"כ $6\cdot16=96$.

תרגיל 2.5 הסתברות מתמורות ⭐⭐
5 ספרים שונים מסודרים באקראי על מדף. מה הסיכוי ששני ספרים מסוימים יהיו צמודים?

פתרון

כל סידור שווה-סיכוי. צמודים: $4!\cdot2=48$ מתוך $5!=120$. לכן $\frac{48}{120}=\frac25$.

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

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

3צירופים: כמה דרכים לבחור?

❓ בכמה דרכים אפשר לבחור ועדה של 3 אנשים מתוך 5, כשלא אכפת לנו מהסדר?

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

שלב 1: מ"סידור" ל"בחירה"

📐 צירופים ($n$ בוחר $k$)

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

$$\binom{n}{k}=\frac{n!}{k!\,(n-k)!}.$$

הסימון $\binom nk$ נקרא "$n$ בוחר $k$".

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

דוגמה: ועדה של 3 מתוך 5. עם סדר: $5\cdot4\cdot3=60$. כל ועדה נספרה $3!=6$ פעמים, ולכן $\frac{60}{6}=10$. בנוסחה: $\binom53=\frac{5!}{3!\,2!}=\frac{120}{6\cdot2}=10$ ✔.

שלב 2: ערכים מיוחדים (כדאי לזכור)

שלב 3: הטריק "בחר מקומות"

📐 רצפים בינאריים עם $k$ אחדות

מספר הרצפים באורך $n$ מעל $\{0,1\}$ שיש בהם בדיוק $k$ אחדות הוא $\binom nk$.

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

דוגמה: 4 הטלות מטבע עם בדיוק 2 עצים (H). בוחרים 2 מקומות מתוך 4: $\binom42=6$. הרצפים: HHTT, HTHT, HTTH, THHT, THTH, TTHH.

💡 אינטואיציה

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

שלב 4: כלל פסקל

📐 כלל פסקל

לכל $1\le k\le n-1$:

$$\binom nk=\binom{n-1}{k-1}+\binom{n-1}{k}.$$

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

💡 הוכחה קומבינטורית ("סיפור הוועדה")

נבחר ועדה של $k$ מתוך $n$ אנשים, ונתמקד באדם אחד, X. שני מקרים זרים:

לפי כלל החיבור, הסכום הוא כל הוועדות, $\binom nk$. (שיטה כללית: אם סופרים את אותו הדבר בשתי דרכים, מקבלים זהות.)

📐 הוכחה אלגברית (צעד אחר צעד)

צעד 1. נפתח את שני האגפים לפי ההגדרה:

$$\binom{n-1}{k-1}+\binom{n-1}{k}=\frac{(n-1)!}{(k-1)!\,(n-k)!}+\frac{(n-1)!}{k!\,(n-k-1)!}.$$

צעד 2: מכנה משותף. המכנים שונים. המכנה הנוח הוא $k!\,(n-k)!$. כדי להגיע אליו צריך להשלים גורם בכל שבר, בעזרת הכלל $m!=m\cdot(m-1)!$:

$$=\frac{(n-1)!\cdot k}{k!\,(n-k)!}+\frac{(n-1)!\cdot(n-k)}{k!\,(n-k)!}.$$

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

$$=\frac{(n-1)!\,\big[k+(n-k)\big]}{k!\,(n-k)!}=\frac{(n-1)!\cdot n}{k!\,(n-k)!}=\frac{n!}{k!\,(n-k)!}=\binom nk.\ \ \blacksquare$$

בצעד האחרון השתמשנו שוב ב-$n\cdot(n-1)!=n!$. שים לב שהגורמים $k$ ו-$(n-k)$ מסתכמים ל-$n$, וזה מה שגורם לכל להצטמצם.

לחץ על מספר באמצע שורה במשולש, וראה (בירוק) מהם שני ה"הורים" שלו:

🔺 משולש פסקל

שלב 5: סכום השורה הוא $2^n$

📐 סכום שורה
$$\binom n0+\binom n1+\cdots+\binom nn=2^n.$$

למה? נספור את כל תתי-הקבוצות של קבוצה בת $n$ איברים בשתי דרכים. (א) לפי הגודל: $\binom nk$ תתי-קבוצות בגודל $k$, ולחבר על כל $k$ מ-0 עד $n$. (ב) לכל איבר מחליטים "בפנים/בחוץ": $2^n$ (סעיף 1, שלב 4). שתי הספירות סופרות את אותו הדבר, ולכן שוות.

שלב 6: משפט הבינום

📐 משפט הבינום
$$(a+b)^n=\sum_{k=0}^n\binom nk\,a^k\,b^{n-k}.$$

($\sum_{k=0}^n$ פירושו "סכום על כל $k$ מ-0 עד $n$".)

💡 למה זה נכון? ("בחר מקומות" שוב)

$(a+b)^n$ הוא מכפלה של $n$ סוגריים: $(a+b)(a+b)\cdots(a+b)$. כשפותחים, מכל סוגר בוחרים או $a$ או $b$. כדי לקבל את האיבר $a^kb^{n-k}$ צריך ש-$a$ יבוא מ-$k$ מהסוגריים. ובחירה של איזה $k$ סוגריים נותנים $a$ היא בדיוק "בחר מקומות": $\binom nk$ דרכים. לכן המקדם של $a^kb^{n-k}$ הוא $\binom nk$.

דוגמה, $n=3$: $(a+b)^3=a^3+3a^2b+3ab^2+b^3$, והמקדמים $1,3,3,1$ הם שורה 3 במשולש פסקל.

🤖 למה זה חשוב להסתברות

נציב $a=p$ ו-$b=1-p$ (כש-$p$ הוא מספר בין 0 ל-1): $\big(p+(1-p)\big)^n=1^n=1$. כלומר $\sum_{k=0}^n\binom nkp^k(1-p)^{n-k}=1$. אלה בדיוק ההסתברויות של "כמה הצלחות ב-$n$ ניסיונות בלתי-תלויים, כשהסיכוי להצלחה בכל אחד הוא $p$". המשפט מבטיח שהן מסתכמות ל-1, ולכן זו התפלגות תקפה (ההתפלגות הבינומית). וגם המקדם $\binom nk$ מופיע שם משום שיש $\binom nk$ רצפים עם $k$ הצלחות (הטריק "בחר מקומות").

➕ הרחבה: זהות ונדרמונד, ולמה ההתפלגות ההיפרגאומטרית מתנרמלת

בחפיסה של $N$ קלפים, $K$ מהם "אדומים", בוחרים $n$ קלפים. ספור את כל הבחירות לפי מספר הקלפים האדומים $j$ שנבחרו: בוחרים $j$ מתוך $K$ האדומים וגם $n-j$ מתוך $N-K$ האחרים, ומכפילים: $\binom Kj\binom{N-K}{n-j}$. סכום על כל $j$ סופר את כל הבחירות האפשריות:

$$\sum_j\binom Kj\binom{N-K}{n-j}=\binom Nn.$$

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

🤖 קשר ל-ML

$\binom n2=\frac{n(n-1)}2$ הוא מספר הזוגות. ב-dataset של 1,000 דוגמאות יש $499{,}500$ זוגות, ולכן מטריצת מרחקים בין כולן היא כבר חצי מיליון ערכים (ובמיליון דוגמאות: חמישים מיליארד). זו הסיבה שאלגוריתמים "ריבועיים" ב-$n$ לא מתאימים לדאטה גדול.

תרגול לסעיף 3

תרגיל 3.1 צירופים + משלים ⭐
בוחרים ועדה של 3 מתוך 10 אנשים, ש-4 מהם נשים. בכמה דרכים תהיה לפחות אשה אחת?

פתרון

הכל: $\binom{10}3=120$. בלי נשים כלל (3 מתוך 6 הגברים): $\binom63=20$. התשובה: $120-20=100$.

תרגיל 3.2 כפל של בחירות ⭐⭐
ועדה של 4 מתוך 6 גברים ו-5 נשים, עם בדיוק 2 נשים. כמה ועדות?

פתרון

בוחרים 2 נשים מתוך 5 וגם 2 גברים מתוך 6, ומכפילים: $\binom52\binom62=10\cdot15=150$.

תרגיל 3.3 הוכחה קומבינטורית ⭐⭐⭐
הוכח: $k\binom nk=n\binom{n-1}{k-1}$, בעזרת "ספירה בשתי דרכים". (רמז: ועדה של $k$ עם יו"ר.)

פתרון

נספור את מספר הזוגות (ועדה של $k$ אנשים מתוך $n$, יו"ר מתוכה). דרך א: בוחרים קודם ועדה ($\binom nk$ דרכים), ואז יו"ר מתוכה ($k$ דרכים): $k\binom nk$. דרך ב: בוחרים קודם יו"ר ($n$ דרכים), ואז את שאר $k-1$ חברי הוועדה מתוך $n-1$ הנותרים: $n\binom{n-1}{k-1}$. אותה כמות. ∎

תרגיל 3.4 משפט הבינום ⭐⭐
א. חשב $\sum_{k=0}^n\binom nk2^k$. ב. הוכח $\sum_{k=0}^n(-1)^k\binom nk=0$ עבור $n\ge1$, והסבר קישור לתרגיל 1.3.

פתרון

א. $a=2,b=1$ במשפט הבינום: $(2+1)^n=3^n$. ב. $a=-1,b=1$: $(-1+1)^n=0$. כלומר $\sum_{k\text{ זוגי}}\binom nk=\sum_{k\text{ אי-זוגי}}\binom nk$: מספר תתי-הקבוצות הזוגיות שווה לאי-זוגיות, בדיוק מה שהוכחנו בהתאמה חח"ע.

תרגיל 3.5 זוגות ⭐
10 אנשים נפגשים, וכל אחד לוחץ יד לכל אחד אחר פעם אחת. כמה לחיצות יד?

פתרון

$\binom{10}2=45$. (לא $10\cdot9=90$, זה סופר כל לחיצה פעמיים.)

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

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

4מקדם מולטינומי: חלוקה לכמה קבוצות

❓ בכמה דרכים אפשר לחלק 6 אנשים לשלוש קבוצות מסומנות, בגדלים 3, 2 ו-1?

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

שלב 1: בוחרים קבוצה אחרי קבוצה

קודם בוחרים את הקבוצה בת 3 מבין 6: $\binom63=20$. מבין 3 הנותרים בוחרים את הקבוצה בת 2: $\binom32=3$. ה-1 האחרון הוא הקבוצה השלישית: $\binom11=1$. לפי כלל הכפל: $20\cdot3\cdot1=60$.

נפתח את הנוסחה: $\binom63\binom32\binom11=\frac{6!}{3!\,3!}\cdot\frac{3!}{2!\,1!}\cdot1=\frac{6!}{3!\,2!\,1!}$ (גורמי "$3!$" מצטמצמים).

📐 מקדם מולטינומי
$$\binom{n}{k_1,k_2,\dots,k_m}=\frac{n!}{k_1!\,k_2!\cdots k_m!}\qquad(k_1+\cdots+k_m=n).$$

מספר הדרכים לחלק $n$ פריטים לקבוצות מסומנות בגדלים $k_1,\dots,k_m$.

💡 זה אותו דבר כמו אנגרמות!

זה בדיוק הנוסחה של BANANA: $\frac{6!}{3!\,2!\,1!}$. הקשר: "לסדר אותיות עם חזרות" ו"לחלק מקומות לתוויות" הם אותו דבר. בכל מילה ב-BANANA, "קבוצת ה-A" היא אוסף המקומות שבהם יושבת A. לבחור מילה = לבחור מקומות לכל אות = לחלק את 6 המקומות ל-3 קבוצות מסומנות (A: 3, N: 2, B: 1). וזה "בחר מקומות" בגרסת כמה תוויות.

שלב 2: קבוצות לא מסומנות

אם הקבוצות זהות (אין שמות), חולקים ב-$m!$ כשכולן באותו גודל. למשל 6 אנשים ל-3 זוגות (בלי שמות לזוגות): קודם עם שמות: $\frac{6!}{2!2!2!}=90$. בלי שמות, כל חלוקה נספרה $3!=6$ פעמים (בכל תיוג של הזוגות): $90/6=15$. ("ספור עם עודף וחלק", שוב.)

שלב 3: משפט מולטינומי, והתפלגות מולטינומית

כמו משפט הבינום: $(a_1+\cdots+a_m)^n=\sum\binom{n}{k_1,\dots,k_m}a_1^{k_1}\cdots a_m^{k_m}$ (סכום על כל הצירופים של $k_i$ עם סכום $n$). הנימוק זהה: מכל אחד מ-$n$ הסוגריים בוחרים סוג, והמקדם סופר איזה סוגריים נותנים כל סוג.

🤖 קשר ל-ML: ספירות של קטגוריות

מטילים קובייה $n=6$ פעמים. מה הסיכוי שכל פאה יוצאת בדיוק פעם אחת? יש $\frac{6!}{1!\cdots1!}=720$ רצפים כאלה, והסתברות כל רצף $(1/6)^6$: $\frac{720}{46656}\approx0.0154$. אותה צורה, $\binom{n}{k_1,\dots,k_m}\prod p_i^{k_i}$, היא ההתפלגות המולטינומית: "כמה פעמים כל קטגוריה" בהרבה דגימות, כש-$p_i$ הוא הסיכוי לקטגוריה $i$ בכל דגימה (למשל פלט softmax של מסווג), וגם ספירות מילים במסמך. ההגיון: מספר הרצפים עם הספירות $k_1,\dots,k_m$ הוא המקדם המולטינומי, וכל רצף כזה הסתברותו $\prod p_i^{k_i}$ (הכפלת ההסתברויות, כשהדגימות בלתי-תלויות).

תרגול לסעיף 4

תרגיל 4.1 חלוקה לקבוצות מסומנות ⭐
10 תלמידים מחולקים לקבוצות של 5, 3 ו-2 (לכל קבוצה מטרה שונה). כמה חלוקות?

פתרון

$\frac{10!}{5!\,3!\,2!}=2520$.

תרגיל 4.2 קבוצות לא מסומנות ⭐⭐
12 אנשים מחולקים לשלוש קבוצות של 4, שאין להן שמות. כמה חלוקות?

פתרון

עם שמות: $\frac{12!}{4!\,4!\,4!}=34{,}650$. בלי שמות, מחלקים ב-$3!$: $5{,}775$.

תרגיל 4.3 הסתברות מולטינומית ⭐⭐
קובייה הוגנת מוטלת 12 פעמים. מה הסיכוי שכל פאה תצא בדיוק פעמיים?

פתרון

רצפים עם כל פאה פעמיים: $\frac{12!}{(2!)^6}=7{,}484{,}400$. מתוך $6^{12}=2{,}176{,}782{,}336$ רצפים שוות-סיכוי. התשובה: $\approx0.00344$ (כ-0.34%).

תרגיל 4.4 משפט מולטינומי ⭐⭐
מהו המקדם של $x^2yz$ בפיתוח $(x+y+z)^4$?

פתרון

$\frac{4!}{2!\,1!\,1!}=12$.

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

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

5בחירה עם חזרות: כוכבים וקווים

❓ אני קונה 5 כדורי גלידה בבית קפה עם 3 טעמים. הסדר לא משנה, ומותר לבחור אותו טעם כמה פעמים. כמה "הזמנות" שונות יש?

שלב 1: מה בעצם סופרים?

רק מספר הכדורים מכל טעם: שלשה $(x_1,x_2,x_3)$ של מספרים לא שליליים עם סכום 5. למשל $(2,1,2)$ הוא "שני כדורי וניל, אחד שוקולד, שניים תות". כמה שלשות כאלה?

שלב 2: הטריק, כוכבים וקווים

נצייר כל כדור כ-★, ונפריד בין הטעמים ב"קווים" |. כל הזמנה הופכת לרצף:

★★ | ★ | ★★   =  (2,1,2)

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

$$\binom{5+3-1}{3-1}=\binom72=21.$$
📐 כוכבים וקווים

מספר הדרכים לחלק $n$ פריטים זהים ל-$k$ תאים (מספר הפתרונות השלמים הלא-שליליים של $x_1+\cdots+x_k=n$):

$$\binom{n+k-1}{k-1}=\binom{n+k-1}{n}.$$
💡 אינטואיציה

הטריק המרכזי: להפוך בעיה חדשה לבעיה שכבר פתרנו. כל הזמנה מתורגמת לרצף של כוכבים וקווים, ו"כמה רצפים עם $k-1$ קווים בין $n+k-1$ מקומות" היא בעיית צירופים. בעיות עם "חלוקה של פריטים זהים" הן ברובן כוכבים וקווים.

⭐ מציג כוכבים וקווים

שלב 3: וריאציות

שלב 4: המלכודת, מה "זהה" ומה "שונה"

⚠️ אי-הבנה נפוצה

5 ממתקים ל-3 ילדים. כמה דרכים?

הכלל: קודם תשאל "האם הפריטים מובחנים?". זו ההבחנה בין $k^n$ ל-$\binom{n+k-1}{k-1}$.

🤖 קשר ל-ML

Bag-of-words: מסמך באורך $n$ מילים וכל מילה מאוצר מילים בגודל $V$, כשלא אכפת לנו מסדר המילים (רק כמה פעמים כל מילה). מספר וקטורי הספירה האפשריים הוא $\binom{n+V-1}{V-1}$. לעומת זאת, מספר הרצפים האפשריים הוא $V^n$. אותו עיקרון בהיסטוגרמה: $n$ דגימות ב-$k$ תאים.

תרגול לסעיף 5

תרגיל 5.1 כוכבים וקווים ⭐
6 כדורי גלידה מ-4 טעמים, בלי סדר ועם חזרות. כמה הזמנות?

פתרון

$\binom{6+4-1}{4-1}=\binom93=84$.

תרגיל 5.2 פתרונות של משוואה ⭐⭐
כמה פתרונות בשלמים לא שליליים יש ל-$x+y+z=10$? וכמה בשלמים חיוביים (כל אחד ≥1)?

פתרון

לא שליליים: $\binom{12}2=66$. חיוביים: $\binom{9}2=36$ (נותנים 1 לכל אחד, ומחלקים 7 בלי הגבלה: $\binom{9}2$).

תרגיל 5.3 מובחן או זהה? ⭐⭐
מחלקים 4 תפוחים ל-3 ילדים. כמה דרכים אם: (א) התפוחים שונים; (ב) התפוחים זהים; (ג) זהים וכל ילד מקבל לפחות אחד?

פתרון

(א) $3^4=81$. (ב) $\binom{6}{2}=15$. (ג) $\binom{3}{2}=3$ (בוחרים איזה ילד מקבל שני תפוחים).

תרגיל 5.4 מינימום שונה לכל תא ⭐⭐⭐
כמה פתרונות שלמים לא שליליים יש ל-$x_1+x_2+x_3+x_4=12$ עם $x_1\ge2$ ו-$x_2\ge3$?

פתרון

מציבים $x_1'=x_1-2$, $x_2'=x_2-3$ (מורידים את המינימום). הסכום החדש: $12-5=7$ בארבעה תאים בלי הגבלה: $\binom{7+4-1}{3}=\binom{10}3=120$.

תרגיל 5.5 ML: רצפים או ספירות? ⭐⭐
אוצר מילים של 4 מילים, ומסמכים באורך 3. כמה רצפי מילים אפשריים, וכמה וקטורי bag-of-words שונים?

פתרון

רצפים: $4^3=64$. וקטורי ספירה: $\binom{3+4-1}{3}=\binom63=20$. הרבה פחות, כי הרצפים "AAB", "ABA", "BAA" כולם ממופים לאותה ספירה.

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

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

6איך בוחרים כלי? מפת החלטה

❓ קיבלתי בעיית ספירה חדשה. איזה כלי אני מפעיל?

שלב 1: שתי שאלות שמכריעות

כשבוחרים $k$ פריטים מתוך $n$, שתי שאלות קובעות הכל: (1) האם הסדר חשוב? ו-(2) האם מותר לחזור על אותו פריט?

בלי חזרותעם חזרות
סדר חשוב$\dfrac{n!}{(n-k)!}$$n^k$
סדר לא חשוב$\dbinom nk$$\dbinom{n+k-1}{k}$
🧭 בורר נוסחאות

שלב 2: שאלות נוספות לפני שמחליטים

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

אחרי כל חישוב שאל: (א) אם הסדר לא חשוב, האם התשובה קטנה מהגרסה "עם סדר"? (חייבת להיות, כי ספרנו כל קבוצה פחות פעמים.) (ב) מקרה קטן ($n=3$ או $4$): האם אפשר לרשום הכל ולהשוות? ברוב הטעויות הנפוצות (ספירה כפולה, התעלמות מסדר) בדיקה על מקרה קטן חושפת אותן מיד.

★תרגול משולב

בלי כותרת של טכניקה: תחליט בעצמך אילו כלים צריך (הטכניקה רשומה בפתרון).

תרגיל מ.1 ⭐⭐
סיסמה בת 5 תווים: 3 אותיות קטנות שונות זו מזו ואחריהן 2 ספרות (חזרות מותרות). כמה סיסמאות?

פתרון

כפל + סדר חשוב ובלי חזרות. $26\cdot25\cdot24\cdot10\cdot10=1{,}560{,}000$.

תרגיל מ.2 ⭐⭐
מטילים מטבע הוגן 6 פעמים. מה הסיכוי לבדיוק 3 עצים? ולפחות עץ אחד?

פתרון

בחר מקומות + משלים. בדיוק 3 עצים: $\binom63/2^6=\frac{20}{64}=0.3125$. לפחות עץ אחד: $1-\frac1{64}=\frac{63}{64}$.

תרגיל מ.3 ⭐⭐⭐
כמה קודים בני 5 ספרות (0 עד 9, חזרות מותרות) יש עם סכום ספרות 10?

רמז

כוכבים וקווים נותן את כל הפתרונות הלא-שליליים של $d_1+\cdots+d_5=10$, אבל ספרה אחת לא יכולה להיות יותר מ-9. כמה פתרונות "פסולים" יש, כלומר עם $d_i\ge10$?

פתרון

כוכבים וקווים + משלים. בלי הגבלה: $\binom{14}4=1001$. פסולים: ספרה אחת שווה 10 (והשאר 0): 5 אפשרויות. (שתי ספרות ≥10 היו נותנות סכום ≥20, בלתי אפשרי.) התשובה: $1001-5=996$.

תרגיל מ.4 ⭐⭐
מחלקים 8 אנשים לשתי קבוצות של 4 בלי שמות לקבוצות. כמה חלוקות? מה אם לקבוצות יש שמות?

פתרון

צירופים + חלוקה בסימטריה. עם שמות: $\binom84=70$. בלי שמות: כל חלוקה נספרה פעמיים: $70/2=35$.

7סיכום ארגז הכלים

המצבהכליהנוסחה
מקרים זרים ("או")חיבור$a+b$
שלבים ברצף ("וגם")כפל$a\cdot b$
קשה לספור ישירותמשליםהכל − לא רוצים
סידור $n$ פריטיםעצרת$n!$
סידור $k$ מתוך $n$תמורה חלקית$\frac{n!}{(n-k)!}$
בחירה בלי סדרצירוף$\binom nk$
אותיות חוזרות / קבוצות מסומנותמולטינומי$\frac{n!}{k_1!\cdots k_m!}$
בלי סדר, עם חזרות (פריטים זהים)כוכבים וקווים$\binom{n+k-1}{k-1}$
שני פריטים צמודיםהדבקהבלוק × סידור פנימי
ספרתי יותר מדיחלוקה בעודףספור עם עודף, חלק
🔭 מה הלאה

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

← מפת הדרכים נספח א2 →