#probability #combinatorics #computer_science

מנייה, צירופים וחלוקות

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

כאשר מרחב המדגם $Ω$ הוא מרחב מדגם שווה הסתברות בדיד. כלומר יש בו מספר סופי של תוצאות שלכל אחת הסתברות זהה. במצב זה ההסתברות של מאורע $A$ תהיה

P (A) = \frac{| A |}{| Ω |}

כאשר נרצה לחשב התסברות של מאורע $A$ עם מספר סופי של תוצאות אפשריות כאשר לכל אחד יש הסתברות $p$ . במצב זה ההסתברות של מאורע $A$ תהיה

p \cdot | A |

דוגמה לחישוב מהסוג הזה היא ה הסתברות בינומית כלומר החישוב של ההתסברות של $k$ heads מבין $n$ הטלות. ראינו שההסתברות לכל מאורע שיניב את התוצאה הזאת מחושבת בקלות בגלל אי תלות. אבל החישוב למספר כל המאורעות שיניבו רצף כזה היא לא כל כך פשוטה.
נתמקד בעקרונות ספירה בסיסיים מהשדה של קומבינטוריקה שאנחנו יכולים לעתים להתקל בהם במודלים הסתברותיים.

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

עקרונות הספירה מבוססים על גישת אלגוריתם פיבונצי, הספירה יורדת למטה לשלב באמצעות עץ. למשל, נניח שיש ניסוי שיש בו שתי שלבים עוקבים. התוצאות האפשריות של השלב הראשון הן $a_{1}, \dots, a_{m}$ והניסויים של השלב השני הם $b_{1}, \dots, b_{n}$ . כעת, התוצאות האפשריות של שתי השלבים הם כל הזוגות הסדורים האפשריים $(a_{i}, b_{j})$ . נשים לב שמספר הזוגות האפשריים הוא $m n$ .
בתמונה ניתן לראות הכללה של הניסוי הנ״ל- הניסוי ממשיך במשך $r$ שלבים כאשר השלב הראשון מכיל $n_{1}$ תוצאות אפשריות וכן הלאה.
Pasted image 20221113215020.png|350

נכליל את עקרונות הספירה כך:
נניח שיש תהליך שמכיל $r$ שלבים

בשלב הראשון יש $n_{1}$ תוצאות אפשריות.
לכל תוצאה אפשרית בשלב הראשון יש $n_{2}$ , תוצאות אפשריות בשלב השני.
באופן כללי, לכל רצף של תוצאות אפשריות ב $i - 1$ השלבים הראשונים יש $n_{i}$ אפשרויות בשלב ה $i$ .

דוגמאות

מספר הסוגים האפשריים למספר טלפון - מספר טלפון הוא בעל 7 ספרות כאשר הספרה הראשונה חייבת להיות שונה מ $0, 1$ . נוכל לתאר את הבעיה הזאת כתיאור של עץ סדרתי כאשר הרמה ה $i$ מייצגת את הספרה ה $i$ ואפשרותיה. כלומר באופן הזה עבור הספרה הראשונה יש לנו 8 אפשרויות וכל השאר עם 10 ולכן נקבל

8 \cdot \underset{6 times}{\underset{⏟}{10 \cdot 10 \dots 10}} = 8 \cdot 10^{6}

מספר תתי הקבוצות לקבוצה בגודל $n$ . נוכל להסתכל על זה כבחירה על כל איבר בקבוצה של האם להכניס אותו לתת הקבוצה או לא. כלומר שישנן $2^{n}$ אפשרויות לבניית תת קבוצה מ $n$ איברים.

מספר דגשים:

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

פרמוטציה מסדר k

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

n (n - 1) (n - 2) \dots (n - k + 1) = \prod_{i = 1}^{k} n - i + 1 \cdot \frac{(n - k) \dots 2 \cdot 1}{(n - k) \dots 2 \cdot 1} = \frac{n!}{(n - k)!}

במקרה הפרטי ש $k = n$ זה פשוט נקרא פרמוטצייה ונקבל $n!$ אפשרויות.

צירופים

נרצה לבנות ועדה של $k$ חברי צוות מקבוצה של $n$ אנשים. ההבדל בין הבעיה הזאת לבעית הפרמוטציות היא שאין חשיבות לסדר הבחירה בכלל כלומר מדובר בבנייה של תת קבוצה. לדוגמה אם נרצה לבנות פרמוטציה מסדר 2 מהאותיות $A, B, C, D$ נקבל

A B, B A, A C, C A, A D, D A, B C, C B, B D, D B, C D, D C

בעוד שבבניית צירוף או תת קבוצה מסדר 2 יש הרבה פחות אפשרויות

A B, A C, A D, B D, B C, C D

נשים לב שקיבצנו כפילויות שבתמורה (פרמוטציה) היו נחשבים לפונקצייה אחרת למשל $A B, B A$ במונחים של תתי קבוצה זה באמת שקול.
נוכל להכליל את הסוגייה הזאת על ידי כך שנשים לב שלכל צירוף יש $k!$ סידורים אפשריים שיחשבו לכפילות (כמו סידור פנימי). כלומר כל שנשאר לעשות הוא לקחת את הביטוי שפיתחנו לפרמוטציה ולחלק ב $k!$ נקבל

\frac{n!}{k! (n - k)!}

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

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

נשים לב לטענה מעניינת בהקשר של: $$p(k)= \binom{n}{k}p^{k}(1-p)^{n-k}$$
זאת הנוסחה שפיתחנו שמאפשרת לחשב את ההסתברות לקבל $k$ heads ב $n$ הטלות מטבע. אמרנו גם שסכום כל ה $k$ האפשריים מ $0$ עד $n$ ייתן $1$ .
אם המטבע הוגן ומתקיים $p = \frac{1}{2}$ אזי יתקיים

\sum_{k = 0}^{n} (\binom{n}{k}) = 2^{n}

זאת בגלל ש $p, 1 - p$ הם שווים וניתן לחבר אותם לפי חוקי חזקות ונקבל $1 / 2^{n}$ ונוכל לפתוח את המקדם הבינומי לפי חוקי סכום, הסכום הזה על המקדם הבינומי מהווה את מספר תתי הקבוצות בגודל $k$ שניתן לבנות מקבוצה בגודל $n$ שזה פשוט ההגדרה לקבוצת החזקה שזה $2^{n}$ .

חשוב לשים לב:

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

חלוקות

נוכל להסתכל על צירוף כ חלוקה של קבוצה ל2 : חלק אחד מכיל $k$ איברים והחלק השני מכיל $n - k$ איברים. כלומר חלוקה זה הכללה לצירוף , בחלוקה נרצה בנוסף להגדיר לכמה חלוקות נרצה לחלק את האוסף. באופן כללי נרצה לקחת $n$ ו $n_{1}, n_{2}, n_{3}, \dots, n_{r}$ מספרים (נשים לכל שכל $n_{i}$ הוא חיובי וסכום $r$ החלוקות הוא $n$ בעצמו). נשים לב ש $n_{i}$ מייצג את כמות האיברים בחלוקה ה $i$ (כלומר יש $r$ חלוקות).
בחלוקה הראשונה יש $(\binom{n}{n_{1}})$ אפשרויות ולאחר מכן נשאר עם $n - n_{1}$ איברים וכן הלאה. כעת נוכל להשתמש בעקרונות ספירה על תהליך עם $r$ שלבים ונכפיל בין כל הבחירות האפשריות בכל שלב ונקבל

(\binom{n}{n_{1}}) (\binom{n - n_{1}}{n_{2}}) (\binom{n - n_{1} - n_{2}}{n_{3}}) \cdot (\binom{n - n_{1} - \dots - n_{r - 1}}{n_{r}})

אם נפתח את זה נקבל

\frac{n!}{\prod_{i = 1}^{r} n_{i}!}

זה נקרא מקדם מולטינומי ונרשום אותו כך

(\binom{n}{n_{1}, n_{2}, n_{3}, n_{4}, \dots, n_{r}})