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

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

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

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

דוגמא: נתון כד ובו 50 כדורים ממוספרים. מה הסיכוי להוציא שני כדורים בעלי מספרים עוקבים מהכד בשתי משיכות?
תשובה: נמנה את מספר האפשרויות להוציא שני כדורים כלשהם מהכד (נסמן מספר זה ב־n), ונמנה את מספר האפשרויות להוציא שני כדורים שמספריהם עוקבים (נסמן מספר זה ב־m), אז הסיכוי להוציא שני כדורים שמספריהם עוקבים הוא ${\frac {m}{n}}$ .

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

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

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

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

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

הגדרה: עצרת

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

למה

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

k־תמורה

במחשבונים, פעולה זו מסומנת בכפתור עם הכתובית "nPr", כך שיש להקליד, למשל, 4P2.

נניח שאנו מוציאים מכד ובו $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)\times \cdots \times (n-k+1)={\frac {n!}{(n-k)!}}

תמורה מעגלית

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

(n-1)!

k־צירוף

במחשבונים, פעולה זו מסומנת בכפתור עם הכתובית "nCr", כך שיש להקליד, למשל, 4C2.

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

למה

מספר האפשרויות לבחור $k$ אברים מתוך $n$ ללא חזרות וללא חשיבות לסדר הוא:

C_{n}^{k}={\binom {n}{k}}\equiv {\frac {P(n,k)}{k!}}={\frac {n!}{k!(n-k)!}}

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

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

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

נתונים $n$ עצמים מ־ $r$ סוגים שונים: $k_{1}$ מסוג 1,... $k_{r}$ מסוג $r$ . מתקיים $k_{1}+\cdots +k_{r}=n$ . מספר הסידורים השונים, כשאיננו מתחשבים בסידור הפנימי של עצמים מאותו סוג.

{\binom {n}{k_{1}}}{\binom {n-k_{1}}{k_{2}}}{\binom {n-k_{1}-k_{2}}{k_{3}}}\times \cdots \times {\binom {k_{r}}{k_{r}}}={\frac {n!}{k_{1}!\times \cdots \times k_{r}!}}

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

למה

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

דוגמאות:

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

למה

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

דוגמאות:

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

סיכום

סידור:

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

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

מספר אפשרויות:	בלי חשיבות לסדר	עם חשיבות לסדר
בלי חזרות	${\binom {n}{k}}={\frac {n!}{k!(n-k)!}}$	${\frac {n!}{(n-k)!}}$
עם חזרות	${\binom {k+n-1}{k}}={\frac {(k+n-1)!}{k!(n-1)!}}$	$n^{k}$