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

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

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

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

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

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

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

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

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

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

תבנית:מבנה תבנית

k־תמורה

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

תבנית:מבנה תבנית

תמורה מעגלית

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

(n - 1)!

k־צירוף

תבנית:תזכורת נניח שבכד נמצאים $n$ כדורים ממוספרים ואנו מוציאים $k$ כדורים, ללא החזרת כדורים לכד וללא חשיבות לסדר ההוצאה. (כמובן $k < n$ ) כמה אפשרויות יש?תבנית:ש תשובה: מספר האפשרויות לבחור $k$ אברים ללא חזרות ועם חשיבות לסדר הבחירה: $P (n, k)$ . נחלק מספר זה במספר הסידורים ל־ $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} + \dots + k_{r} = n$ . מספר הסידורים השונים, כשאיננו מתחשבים בסידור הפנימי של עצמים מאותו סוג.

(\binom{n}{k_{1}}) (\binom{n - k_{1}}{k_{2}}) (\binom{n - k_{1} - k_{2}}{k_{3}}) \times \dots \times (\binom{k_{r}}{k_{r}}) = \frac{n!}{k_{1}! \times \dots \times k_{r}!}

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

תבנית:מבנה תבנית

דוגמאות:

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

תבנית:מבנה תבנית

דוגמאות:

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

סיכום

סידור:

סוג הסידור	מספר האפשרויות
$n$ עצמים בשורה	$n!$
$n$ עצמים במעגל	$(n - 1)!$
$n$ עצמים מ־ $r$ סוגים, בשורה	$\frac{n!}{k_{1}! \times \dots \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}$

תורת הקבוצות

חוקי פילוג

A \cap (B \cup 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}

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

{(⋂_{1}^{n} E_{i})}^{c} = ⋃_{1}^{n} E_{i}^{c}

{(⋃_{1}^{n} E_{i})}^{c} = ⋂_{1}^{n} E_{i}^{c}

ראו גם

תבנית:הסתברות

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

תוכן עניינים

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

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

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

k־תמורה

תמורה מעגלית

k־צירוף

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

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

סיכום

תורת הקבוצות

חוקי פילוג

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

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

ראו גם

תפריט ניווט

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

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

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

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

k־תמורה

תמורה מעגלית

k־צירוף

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

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

סיכום

תורת הקבוצות

חוקי פילוג

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

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

ראו גם

תפריט ניווט

חיפוש