קומבינטוריקה בשביל הסתברות: חיבור, כפל, תמורות, צירופים, מקדם מולטינומי וכוכבים וקווים. זמן משוער: כ-2.5 שעות כולל התרגול. דרישות קדם: אין.
נתחיל ממה שהספירה בכלל משרתת. בהרבה בעיות הסתברות כל התוצאות האפשריות שוות-סיכוי (הטלת קובייה הוגנת, שליפת קלף מחפיסה מעורבבת). אז ההסתברות של מאורע היא פשוט שבר:
$$P(\text{המאורע})=\frac{\text{מספר התוצאות שמתאימות למאורע}}{\text{מספר כל התוצאות האפשריות}}.$$למשל הסיכוי לקבל מספר זוגי בקובייה הוא $\frac36$: 3 תוצאות מתאימות (2, 4, 6) מתוך 6. כלומר חצי מההסתברות היא ספירה: צריך לדעת לספור בלי לרשום את כל התוצאות. בידי פוקר, למשל, יש 2,598,960 תוצאות, ואי אפשר לרשום אותן.
הספירה חוזרת גם בלימוד מכונה (ML): במספר ה-labelings האפשריים של דאטה, בגודל מרחב ההשערות, ובהתפלגויות הבינומית, המולטינומית וההיפרגאומטרית (בעצם, ספירה משוקללת).
הנספח הזה הוא ארגז כלים מלא ועצמאי: לא צריך להכיר שום חומר קודם. כל מושג מוגדר כאן בפעם הראשונה שהוא מופיע, ולכל כלי יש נוסחה כללית, דוגמה והסבר למה הוא עובד. אפשר לקרוא ברצף או לחזור כשצריך. הוא נחלק לשניים: א1 (הדף הזה) הוא היסודות, וא2 הוא כלים מתקדמים ויישומים להסתברות.
| כלי | השימוש |
|---|---|
| כפל ומשלים | כמעט כל חישוב הסתברות |
| צירופים ומשפט הבינום | ההתפלגות הבינומית ("כמה הצלחות ב-$n$ ניסיונות") ונרמולה |
| מקדם מולטינומי | ההתפלגות המולטינומית וספירות מילים |
| כוכבים וקווים | bag-of-words, היסטוגרמות, חלוקת "תקציב" |
| תמורות | ערבוב דאטה, מבחני פרמוטציה, חישוב $n!$ בלוגים |
כמעט כל בעיית ספירה היא אחת משלוש פעולות: "או" = לחבר, "וגם / אחר כך" = להכפיל, "ספרתי יותר מדי" = לחלק. כל השאר הם וריאציות.
❓ כמה "דרכים" יש לעשות משהו, כשאי אפשר לרשום אותן אחת-אחת?
נלך בשלבים: (1) כלל החיבור, (2) כלל הכפל, (3) הספירה בחיסור (משלים), (4) התאמה חח"ע, (5) ספירה עם עודף. הסימון $|A|$ פירושו "מספר האיברים בקבוצה $A$".
צריך לבחור פריט אחד, והוא יכול להיות מסוג 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).
תהליך מורכב מ-$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. זה מספיק.
שאל את עצמך: האם אני בוחר אחד מבין כמה מקרים (חיבור) או מבצע כמה בחירות ברצף (כפל)? "עוגה או גלידה" = חיבור. "חולצה וגם מכנס" = כפל. הטעות הנפוצה ביותר בקומבינטוריקה היא להחליף ביניהם.
כשקשה לספור ישירות, סופרים את ההפך וחוסרים. דוגמה: כמה קודי PIN בני 4 ספרות יש עם לפחות ספרה חוזרת אחת? ישירות זה מסובך (איזו ספרה? כמה פעמים?). בחיסור: כל הקודים הם $10^4=10{,}000$ (כלל הכפל). "הרעים" הם הקודים בלי חזרות בכלל: $10\cdot9\cdot8\cdot7=5{,}040$. לכן $10{,}000-5{,}040=4{,}960$.
אם אפשר להתאים לכל איבר בקבוצה $A$ איבר אחד ויחיד בקבוצה $B$, וכל איבר ב-$B$ מתאים לאיבר אחד ויחיד ב-$A$, אז $|A|=|B|$. (התאמה כזו נקראת חד-חד-ערכית ועל.)
המשמעות: אפשר לספור קבוצה אחרת שיש לה בדיוק אותה כמות, אם היא קלה יותר לספירה.
כמה תתי-קבוצות יש לקבוצה בת $n$ איברים? לכל איבר מחליטים "בפנים" או "בחוץ", כלומר רצף של $n$ כן/לא. תתי-קבוצות ↔ רצפים בינאריים באורך $n$ (כל מקום: 0 או 1). לרצפים אפשר להפעיל את כלל הכפל: $2\cdot2\cdots2=2^n$. לכן יש $2^n$ תתי-קבוצות.
אם ספרנו כל פריט (שרצינו לספור) בדיוק $r$ פעמים, אז המספר האמיתי הוא:
$$\text{המספר האמיתי}=\frac{\text{מה שספרנו}}{r}.$$דוגמה: $n$ אנשים נפגשים, וכל זוג לוחץ יד פעם אחת. כמה לחיצות? נספור "כל אדם לוחץ יד לכל אחד אחר": $n(n-1)$ (לכל אחד מ-$n$ אנשים, $n-1$ אחרים). אבל כל לחיצה נספרה פעמיים (פעם מכל צד). לכן $\frac{n(n-1)}{2}$. ל-$n=10$: $45$.
הדרישה החשובה: כל פריט נספר אותו מספר פעמים. הטכניקה הזו תחזור בתמורות עם אותיות חוזרות, בצירופים ובשולחן עגול.
תרגיל 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$ (פשוט כל תלמיד בכיתה). הכפל היה נכון לשאלה אחרת: "כמה זוגות (בן, בת) אפשר ליצור".
יש לנו כפל לספירה "בשלבים". עכשיו נתמקד בבעיה שחוזרת הכי הרבה: סידור פריטים בשורה.
❓ בכמה דרכים אפשר לסדר 5 אנשים בשורה?
נלך בשלבים: (1) עצרת, (2) סידור חלקי, (3) "הדבקה", (4) אותיות חוזרות, (5) שולחן עגול. בכל שלב: קודם הנוסחה הכללית, אחר כך למה היא נכונה, ואז דוגמה.
$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).
בוחרים $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$.
מסדרים $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!$: התשובה $4!=24$.
יש $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.$$נסה בעצמך:
$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$.
ערבוב דאטה לפני אימון (shuffle) הוא בחירה של אחת מתוך $N!$ תמורות. כל פעם שמוסיפים random seed, בעצם מציינים איזו תמורה בוחרים. מבחני פרמוטציה (permutation tests) בודקים אם תוצאה יכולה להיות מקרית על ידי ערבוב התוויות הרבה פעמים, ותלויים בכך שמספר התמורות עצום.
תרגיל 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 אנשים מתוך 5, כשלא אכפת לנו מהסדר?
נלך בשלבים: (1) הנוסחה, (2) ערכים מיוחדים, (3) הטריק "בחר מקומות", (4) כלל פסקל, (5) סכום השורה, (6) משפט הבינום.
מספר הדרכים לבחור קבוצה של $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$ ✔.
מספר הרצפים באורך $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.
זה אחד הטריקים הכי שימושיים: להפוך כל בעיה של "סידור עם שני סוגי פריטים" לבחירה של מקומות. הוא יחזור בהתפלגות הבינומית, במסלולי סריג, ובשיטת "כוכבים וקווים".
לכל $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)!$:
צעד 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$, וזה מה שגורם לכל להצטמצם.
לחץ על מספר באמצע שורה במשולש, וראה (בירוק) מהם שני ה"הורים" שלו:
למה? נספור את כל תתי-הקבוצות של קבוצה בת $n$ איברים בשתי דרכים. (א) לפי הגודל: $\binom nk$ תתי-קבוצות בגודל $k$, ולחבר על כל $k$ מ-0 עד $n$. (ב) לכל איבר מחליטים "בפנים/בחוץ": $2^n$ (סעיף 1, שלב 4). שתי הספירות סופרות את אותו הדבר, ולכן שוות.
($\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.
$\binom n2=\frac{n(n-1)}2$ הוא מספר הזוגות. ב-dataset של 1,000 דוגמאות יש $499{,}500$ זוגות, ולכן מטריצת מרחקים בין כולן היא כבר חצי מיליון ערכים (ובמיליון דוגמאות: חמישים מיליארד). זו הסיבה שאלגוריתמים "ריבועיים" ב-$n$ לא מתאימים לדאטה גדול.
תרגיל 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$, זה סופר כל לחיצה פעמיים.)
צירופים מחלקים את העולם לשני חלקים: "נבחרו" ו"לא נבחרו". מה אם יש כמה קבוצות (חלוקה לצוותים, אותיות בכמה סוגים)? זה הרחבה טבעית.
❓ בכמה דרכים אפשר לחלק 6 אנשים לשלוש קבוצות מסומנות, בגדלים 3, 2 ו-1?
קבוצות מסומנות הן קבוצות עם שם או תפקיד שונה (למשל "צוות א", "צוות ב", "צוות ג"), כך ש"דנה בצוות א" שונה מ"דנה בצוות ב". (קבוצות לא מסומנות, בלי שמות, בשלב 2.)
קודם בוחרים את הקבוצה בת 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!$" מצטמצמים).
מספר הדרכים לחלק $n$ פריטים לקבוצות מסומנות בגדלים $k_1,\dots,k_m$.
זה בדיוק הנוסחה של BANANA: $\frac{6!}{3!\,2!\,1!}$. הקשר: "לסדר אותיות עם חזרות" ו"לחלק מקומות לתוויות" הם אותו דבר. בכל מילה ב-BANANA, "קבוצת ה-A" היא אוסף המקומות שבהם יושבת A. לבחור מילה = לבחור מקומות לכל אות = לחלק את 6 המקומות ל-3 קבוצות מסומנות (A: 3, N: 2, B: 1). וזה "בחר מקומות" בגרסת כמה תוויות.
אם הקבוצות זהות (אין שמות), חולקים ב-$m!$ כשכולן באותו גודל. למשל 6 אנשים ל-3 זוגות (בלי שמות לזוגות): קודם עם שמות: $\frac{6!}{2!2!2!}=90$. בלי שמות, כל חלוקה נספרה $3!=6$ פעמים (בכל תיוג של הזוגות): $90/6=15$. ("ספור עם עודף וחלק", שוב.)
כמו משפט הבינום: $(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$ הסוגריים בוחרים סוג, והמקדם סופר איזה סוגריים נותנים כל סוג.
מטילים קובייה $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.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 כדורי גלידה בבית קפה עם 3 טעמים. הסדר לא משנה, ומותר לבחור אותו טעם כמה פעמים. כמה "הזמנות" שונות יש?
רק מספר הכדורים מכל טעם: שלשה $(x_1,x_2,x_3)$ של מספרים לא שליליים עם סכום 5. למשל $(2,1,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$ מקומות" היא בעיית צירופים. בעיות עם "חלוקה של פריטים זהים" הן ברובן כוכבים וקווים.
5 ממתקים ל-3 ילדים. כמה דרכים?
הכלל: קודם תשאל "האם הפריטים מובחנים?". זו ההבחנה בין $k^n$ ל-$\binom{n+k-1}{k-1}$.
Bag-of-words: מסמך באורך $n$ מילים וכל מילה מאוצר מילים בגודל $V$, כשלא אכפת לנו מסדר המילים (רק כמה פעמים כל מילה). מספר וקטורי הספירה האפשריים הוא $\binom{n+V-1}{V-1}$. לעומת זאת, מספר הרצפים האפשריים הוא $V^n$. אותו עיקרון בהיסטוגרמה: $n$ דגימות ב-$k$ תאים.
תרגיל 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" כולם ממופים לאותה ספירה.
יש לנו עכשיו ארבעה כלים בסיסיים: כפל, תמורות, צירופים וכוכבים וקווים (ועוד מולטינומי). הבעיה בבעיות אמיתיות: איזה מהם?
❓ קיבלתי בעיית ספירה חדשה. איזה כלי אני מפעיל?
כשבוחרים $k$ פריטים מתוך $n$, שתי שאלות קובעות הכל: (1) האם הסדר חשוב? ו-(2) האם מותר לחזור על אותו פריט?
| בלי חזרות | עם חזרות | |
|---|---|---|
| סדר חשוב | $\dfrac{n!}{(n-k)!}$ | $n^k$ |
| סדר לא חשוב | $\dbinom nk$ | $\dbinom{n+k-1}{k}$ |
אחרי כל חישוב שאל: (א) אם הסדר לא חשוב, האם התשובה קטנה מהגרסה "עם סדר"? (חייבת להיות, כי ספרנו כל קבוצה פחות פעמים.) (ב) מקרה קטן ($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$.
| המצב | הכלי | הנוסחה |
|---|---|---|
| מקרים זרים ("או") | חיבור | $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 מאורעות ויותר, בעיית הכובעים, שובך יונים, מסלולי סריג, ספירה לשם חישוב הסתברות (ידי פוקר, בחירה בלי החזרה), וקצב הגדילה של העצרת (סטירלינג) שמופיע באנטרופיה.