הסתברות/מבוא

מתוך ויקיספר, אוסף ספרי הלימוד והמדריכים החופשי.

תוכן עניינים

1 קומבינטוריקה
2 תורת הקבוצות
3 ראו גם

[עריכה] קומבינטוריקה

בבואנו לבנות מודל הסתברותי, לעיתים קרובות עלינו למנות על מספר האפשרויות הקימות לכל ארוע.
דוגמא: נתון כד ובו 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-תמורה

במחשבונים, פעולה זו מסומנת בכפתור עם הכתובית "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)...(n-k+1)={n!\over (n-k)!}$

[עריכה] תמורה מעגלית

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

$\ (n-1)!$

[עריכה] k-צירוף

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

נניח שבכד נמצאים 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$ .

דוגמאות:

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