הסתברות/חומר רקע

קומבינטוריקה

בבואנו לבנות מודל הסתברותי, לעיתים קרובות עלינו למנות על מספר האפשרויות הקימות לכל ארוע.
דוגמא: נתון כד ובו 50 כדורים ממוספרים. מה הסיכוי להוציא שני כדורים בעלי מספרים עוקבים מהכד בשתי משיכות? תשובה: נמנה את מספר האפשרויות להוציא שני כדורים כלשהם מהכד (נסמן מספר זה ב-n), ונמנה את מספר האפשרויות להוציא שני כדורים שמספריהם עוקבים (נסמן מספר זה ב-m), אז הסיכוי להוציא שני כדורים שמספריהם עוקבים הוא $m \over n$.
תורת הקומבינטוריקה היא תורה שעוסקת במניית אפשרויות. בספר זה איננו מלמדים קומבינטוריקה לעומק, אך כיוון שהדבר חשוב לבניית מודלים הסתברותיים נסביר על מספר מודלים בסיסיים בקומבינטוריקה.

עקרונות החיבור והכפל בקומבינטוריקה

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

סידור n עצמים בשורה

נניח שאנו מסדרים n כדורים ממוספרים בשורה. כמה אפשרויות יש? תשובה: בתא הראשון ניתן לשים אחד מבין n הכדורים. כעת נותרו n-1 תאים, ו-n-1 כדורים, לכן בתא השני ישנם רק n-1 כדורים אפשריים. לתא השלישי n-2 כדורים וכן הלאה עד שיגמרו הכדורים. לכן ישנן: $n\times (n-1)\times (n-2)\times \cdots \times 1$ אפשרויות.

הגדרה: עצרת נסמן את המכפלה $n!\equiv n\times (n-1)\times (n-2)\times \cdots \times 1$ ונכנה אותה n-עצרת.

למה מספר האפשרויות לסדר n איברים שונים בשורה הוא $\ n!$

k-תמורה

תבנית:גזור ושמור נניח שאנו מוציאים מכד ובו n כדורים ממוספרים k כדורים ללא החזרת כדורים לכד ועם חשיבות לסדר ההוצאה. (כמובן ש- $\ k<n$) כמה אפשרויות יש?
תשובה: עבור הכדור הראשון יש n אפשרויות, לכדור השני יש n-1 אפשרויות כך עד הכדור ה-n-k-1 כאשר אז הוצאו כבר k כדורים. קל לראות שהתוצאה הזו ניתנת לכתיבה ע"י:

למה מספר האפשרויות לבחור k איברים מתוך n איברים שונים כאשר הבחירה היא עם חשיבות לסדר וללא החזרה הוא: $A_{n}^{k}=P(n,k)\equiv n(n-1)(n-2)...(n-k+1)={n! \over (n-k)!}$

תמורה מעגלית

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

$\ (n-1)!$

k-צירוף

תבנית:גזור ושמור נניח שבכד נמצאים n כדורים ממוספרים ואנו מוציאים k כדורים, ללא החזרת כדורים לכד וללא חשיבות לסדר ההוצאה. (כמובן ש- $\ k<n$) כמה אפשרויות יש?
תשובה: מספר האפשרויות לבחור k איברים ללא חזרות וללא חשיבות לסדר הבחירה: $\ P(n,k)$. נחלק מספר זה במספר הסידורים ל-k איברים (כי לנו אין חשיבות לסדר) ונקבל:

למה מספר האפשרויות לבחור k איברים מתוך n ללא חזרות וללא חשיבות לסדר הוא: $\ C_{n}^{k}={n \choose k}\equiv {P(n,k) \over k!}={n! \over k!(n-k)!}$

הגודל $\ {n \choose k}$ נקרא המקדם הבינומי ולכל n,k מתקיים: $\ {n \choose k}={n \choose n-k}$.

דוגמה נוספת: מספר האפשרויות לבחור שני איברים מתוך השלשה a,b,c, כאשר הבחירה היא ללא חשיבות לסדר וללא החזרה, הוא 3: a,b; a,c; b,c.

תמורות עם חזרות

נתונים n עצמים מ-r סוגים שונים: k₁ מסוג 1,... k_r מסוג r. מתקיים k₁+...+k_r=n. מספר הסידורים השונים, כשאיננו מתחשבים בסידור הפנימי של עצמים מאותו סוג.

$\ {n \choose k_{1}}{n-k_{1} \choose k_{2}}{n-k_{1}-k_{2} \choose k_{3}}...{k_{r} \choose k_{r}}={n! \over k_{1}!k_{2}!...k_{r}!}$

חלוקת כדורים לתאים

למה מספר האפשרויות לבחור k איברים מתוך n איברים שונים, כאשר הבחירה היא עם חשיבות לסדר ועם החזרה הוא $\ n^{k}$.

דוגמאות:

1. מספר האופנים לחלק k כדורים ל-n תאים, כאשר הכדורים שונים.
2. כמות המספרים שניתן לייצג באמצעות n ספרות בבסיס k:
   באמצעות 3 ספרות דצימליות ניתן לייצג $\ 10^{3}=1000$ ספרות.

למה מספר האפשרויות לבחור k איברים מתוך n איברים שונים, כאשר הבחירה היא ללא חשיבות לסדר ועם החזרה הוא $\ {k+n-1 \choose k}={(k+n-1)! \over k!(n-1)!}$

דוגמאות:

1. מספר האופנים לחלק k כדורים זהים ל-n תאים.

סיכום

סידור:

סוג הסידור	מספר האפשרויות
n עצמים בשורה	$\ n!$
n עצמים במעגל	$\ (n-1)!$
n עצמים מ-r סוגים, בשורה	$\ n! \over k_{1}!k_{2}!...k_{r}!$

בחירת k מתוך n:

חזרות?	חשיבות לסדר?	מספר האפשרויות
		$\ n! \over (n-k)!$
		$\ {n \choose k}={n! \over k!(n-k)!}$
		$\ n^{k}$
		$\ {k+n-1 \choose k}={(k+n-1)! \over k!(n-1)!}$

תורת הקבוצות

חוקי פילוג

$\ A\cap (B\cap C)=(A\cap B)\cup (A\cap C)$

$\ A\cup (B\cap C)=(A\cup B)\cap (A\cup C)$

חוקי דה-מורגן

$(E_{1}\cup E_{2})^{c}=E_{1}^{c}\cap E_{2}^{c}$

$(E_{1}\cap E_{2})^{c}=E_{1}^{c}\cup E_{2}^{c}$

הכללה של דה-מורגן

$\ \left(\bigcap _{1}^{n}E_{i}\right)^{c}=\bigcup _{1}^{n}E_{i}^{c}$

$\ \left(\bigcup _{1}^{n}E_{i}\right)^{c}=\bigcap _{1}^{n}E_{i}^{c}$

ראו גם

• תורת הקבוצות
• אלגברה תיכונית/קומבינטוריקה