הצגת המקור של הדף "הסתברות/חומר רקע"

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

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

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

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

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

===סידור n עצמים בשורה===
נניח שאנו מסדרים <math>n</math> כדורים ממוספרים בשורה. כמה אפשרויות יש?{{ש}}
תשובה: בתא הראשון ניתן לשים אחד מבין <math>n</math> הכדורים. כעת נותרו <math>n-1</math> תאים ו־<math>n-1</math> כדורים, לכן בתא השני ישנם רק <math>n-1</math> כדורים אפשריים. לתא השלישי <math>n-2</math> כדורים וכן הלאה עד שיגמרו הכדורים. לכן ישנן:
<math>n(n-1)(n-2)\times\cdots\times1</math> אפשרויות.
{{הגדרה|שם=עצרת|
תוכן=נסמן את המכפלה <math>n!\equiv n(n-1)(n-2)\times\cdots\times1</math> ונכנה אותה '''n־עצרת'''.}}
{{למה|תוכן=מספר האפשרויות לסדר <math>n</math> אברים שונים בשורה הוא <math>n!</math>}}

===k־תמורה===
{{תזכורת|במחשבונים, פעולה זו מסומנת בכפתור עם הכתובית "n'''P'''r", כך שיש להקליד, למשל, 4'''P'''2.}}
נניח שאנו מוציאים מכד ובו <math>n</math> כדורים ממוספרים, <math>k</math> כדורים ללא החזרת כדורים לכד ו'''עם חשיבות''' לסדר ההוצאה. (כמובן <math>k<n</math>) כמה אפשרויות יש?{{ש}}
תשובה: עבור הכדור הראשון יש <math>n</math> אפשרויות, לכדור השני יש <math>n-1</math> אפשרויות כך עד הכדור ה־<math>n-(k-1)</math> כאשר אז הוצאו כבר <math>k</math> כדורים. קל לראות שהתוצאה הזו ניתנת לכתיבה ע"י:
{{למה|תוכן=מספר האפשרויות לבחור <math>k</math> אברים מתוך <math>n</math> אברים שונים כאשר הבחירה היא עם חשיבות לסדר וללא החזרה הוא:
:<math>A_n^k=P(n,k)\equiv n(n-1)(n-2)\times\cdots\times(n-k+1)=\frac{n!}{(n-k)!}</math>}}

===תמורה מעגלית===
נניח שאנו מסדרים <math>n</math> כדורים ממוספרים '''במעגל'''. כעת אין מבחינים בין שני סידורים המובדלים זה מזה על־ידי סיבוב. את התוצאה של תמורה רגילה (עצרת של מספר האברים) נחלק בסוף התהליך במספר המקומות במעגל, שכן במעגל אין משמעות אם נתחיל ממקום זה או אחר ולכן למעשה הבחירה הראשונה חסרת השפעה מבחינת אופי הסידור. לכן מספר האפשרויות:
:<math>(n-1)!</math>

===k־צירוף===
{{תזכורת|במחשבונים, פעולה זו מסומנת בכפתור עם הכתובית "n'''C'''r", כך שיש להקליד, למשל, 4'''C'''2.}}
נניח שבכד נמצאים <math>n</math> כדורים ממוספרים ואנו מוציאים <math>k</math> כדורים, ללא החזרת כדורים לכד ו'''ללא חשיבות''' לסדר ההוצאה. (כמובן <math>k<n</math>) כמה אפשרויות יש?{{ש}}
תשובה: מספר האפשרויות לבחור <math>k</math> אברים ללא חזרות ועם חשיבות לסדר הבחירה: <math>P(n,k)</math>. נחלק מספר זה במספר הסידורים ל־<math>k</math> אברים (כי לנו אין חשיבות לסדר) ונקבל:
{{למה|תוכן=מספר האפשרויות לבחור <math>k</math> אברים מתוך <math>n</math> ללא חזרות וללא חשיבות לסדר הוא:
:<math>C_n^k=\binom{n}{k}\equiv\frac{P(n,k)}{k!}=\frac{n!}{k!(n-k)!}</math>}}
הגודל <math>\binom{n}{k}</math> נקרא המקדם הבינומי ולכל <math>n,k</math> מתקיים: <math>\binom{n}{k}=\binom{n}{n-k}</math>.

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

===תמורות עם חזרות===
נתונים <math>n</math> עצמים מ־<math>r</math> סוגים שונים: <math>k_1</math> מסוג 1,... <math>k_r</math> מסוג <math>r</math>. מתקיים <math>k_1+\cdots+k_r=n</math>. מספר הסידורים השונים, כשאיננו מתחשבים בסידור הפנימי של עצמים מאותו סוג.
:<math>\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!}</math>

===חלוקת כדורים לתאים===
{{למה|תוכן=מספר האפשרויות לבחור <math>k</math> אברים מתוך <math>n</math> אברים שונים, כאשר הבחירה היא עם חשיבות לסדר ועם החזרה הוא <math>n^k</math>.}}
'''דוגמאות:'''
#מספר האופנים לחלק <math>k</math> כדורים ל־<math>n</math> תאים, כאשר הכדורים שונים.
#כמות המספרים שניתן לייצג באמצעות <math>k</math> ספרות בבסיס <math>n</math>:{{ש}}באמצעות 3 ספרות דצימליות ניתן ליצג <math>10^3=1000</math> מספרים.

{{למה|תוכן=מספר האפשרויות לבחור <math>k</math> אברים מתוך <math>n</math> אברים שונים, כאשר הבחירה היא ללא חשיבות לסדר ועם החזרה הוא <math>\binom{k+n-1}{k}=\frac{(k+n-1)!}{k!(n-1)!}</math>}}
'''דוגמאות:'''
#מספר האופנים לחלק <math>k</math> כדורים זהים ל־<math>n</math> תאים.

===סיכום===
סידור:
{| class="wikitable" border="1" style="text-align:center"
! סוג הסידור
! מספר האפשרויות
|-
| <math>n</math> עצמים בשורה
| <math>n!</math>
|-
| <math>n</math> עצמים במעגל
| <math>(n-1)!</math>
|-
| <math>n</math> עצמים מ־<math>r</math> סוגים, בשורה
| <math>\frac{n!}{k_1!\times\cdots\times k_r!}</math>
|}

בחירת <math>k</math> מתוך <math>n</math>:
{| class="wikitable" border="1" style="text-align: center"
! מספר אפשרויות:
! בלי חשיבות לסדר
! עם חשיבות לסדר
|-
! בלי חזרות
| <math>\binom{n}{k}=\frac{n!}{k!(n-k)!}</math>
| <math>\frac{n!}{(n-k)!}</math>
|-
! עם חזרות
| <math>\binom{k+n-1}{k}=\frac{(k+n-1)!}{k!(n-1)!}</math>
| <math>n^k</math>
|}

==תורת הקבוצות==
[[Image:Venn diagram ABC BW Explanation.png|שמאל|300 פיקסלים]]

===חוקי פילוג===
:<math>A\cap (B\cup C)=(A\cap B)\cup(A\cap C)</math>
:<math>A\cup(B\cap C)=(A\cup B)\cap(A\cup C)</math>

===חוקי דה־מורגן===
:<math>(E_1\cup E_2)^c=E_1^c\cap E_2^c</math>
:<math>(E_1\cap E_2)^c=E_1^c\cup E_2^c</math>

====הכללה של דה־מורגן====
:<math>\left(\bigcap_1^n E_i\right)^c=\bigcup_1^n E_i^c</math>
:<math>\left(\bigcup_1^n E_i\right)^c=\bigcap_1^n E_i^c</math>

==ראו גם==
*[[תורת הקבוצות]]
*[[מתמטיקה תיכונית/אלגברה תיכונית/קומבינטוריקה|קומבינטוריקה]]

{{הסתברות|מוגבל}}

[[קטגוריה:הסתברות (לאוניברסיטה)]]