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

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

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

• כלל המכפלה
• סידורים בשורה (תמורות, פרמוטציות)
• מודלים לבחירה (קומבינציות)

המונחים באנגלית: Multiplication rule, Permutations, Combinations

מפת התמצאות לשאלות בקומבינטוריקה

העיקרון הבסיסי בחישובים הקומבינטוריים מבוסס על פירוק הניסוי המקרי לשלבים.

כלל המכפלה

כאשר ניסוי מתבצע ב k שלבים בזה אחר זה, וכאשר בשלב הראשון יש n₁ אפשרויות, בשלב השני יש n₂ אפשרויות,…, ובשלב ה k יש n_k אפשרויות, אזי מספר התוצאות השונות בניסוי כולו הוא:

{n_1\cdot
 n_2\cdot\ldots\ \cdot n_k}

במלים פשוטות: מספר התוצאות השונות בניסוי רב-שלבי מחושב ע״י מכפלת מספרי התוצאות האפשריות בכל אחד מהשלבים.

דוגמה: מטילים קוביה פעמיים, ולאחר מכן מטילים מטבע 3 פעמים. זהו ניסוי מקרי עם 5 שלבים. בכל אחד משני השלבים הראשונים יש 6 תוצאות אפשריות, ובכל אחד משלושת השלבים האחרונים יש 2 תוצאות אפשריות. לכן, מספר התוצאות השונות של הניסוי הכולל עם חמשת השלבים הוא:

6\cdot6\cdot2\cdot2\cdot2=288

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

בכמה אפשרויות ניתן לסדר n עצמים שונים בשורה? במלים אחרות: מה מספר הפרמוטציות של n העצמים השונים?

לפי כלל המכפלה, נקבל את התשובה:

n!=n\cdot\left(n-1\right)\cdot\ldots\cdot2\cdot1

דוגמה: בכמה דרכים ניתן לסדר 5 ספרים שונים על מדף?

זהו ניסוי עם 5 שלבים: למקום השמאלי ביותר יש 5 אפשרויות, למקום הבא רק 4 אפשרויות, וכך הלאה. בכל שלב מספר הספרים יורד ב 1, ולכן התשובה היא: 120=!5

מודלים לבחירה

המודלים מספקים נוסחאות לחישוב מספר האפשרויות בהן ניתן לבחור k עצמים מתוך קבוצה של n עצמים שונים.

כדי לדעת מהו המודל המתאים, יש לברר שני דברים:

1. האם הבחירה היא עם חשיבות לסדר או ללא חשיבות לסדר:

עם חשיבות לסדר = יש חשיבות לסדר הבחירה. יש תפקיד/יעוד לכל עצם שנבחר.

ללא חשיבות לסדר = יש משמעות רק לשאלה מי מהעצמים נבחר.

2. האם בחירה היא עם החזרה או ללא החזרה:

עם החזרה = כל עצם יכול להיבחר יותר מפעם אחת.

ללא החזרה = כל עצם יכול להיבחר לכל היותר פעם אחת.

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

מודל 1: בחירה עם חשיבות לסדר וללא החזרה

מספר האפשרויות לבחירה של k עצמים מתוך קבוצה של n עצמים שונים, כאשר הבחירה היא עם חשיבות לסדר וללא החזרה הוא:

\frac{n!}{(n-k)!}=n\cdot(n-1)\cdot\ldots\cdot(n-k+1)

מודל 2: בחירה ללא חשיבות לסדר וללא החזרה

מספר האפשרויות לבחירה של k עצמים מתוך קבוצה של n עצמים שונים, כאשר הבחירה היא ללא חשיבות לסדר וללא החזרה הוא:

\binom{n}{k}=\frac{n!}{k!\left(n-k\right)!}

שימו לב: יש קשר בין מודל 1 למודל 2. כל אפשרות בבחירה ללא חשיבות לסדר מקבילה ל !k אפשרויות כאשר יש חשיבות לסדר. לכן, המעבר ממודל 1 למודל 2 הוא חלוקה במספר הסידורים הפנימיים, שהוא !k.

נוסחאות שימושיות:

\left(\begin{matrix}n\\1\\\end{matrix}\right)=n\ \ \ \ \ \ \ \ \ \ \left(\begin{matrix}n\\n\\\end{matrix}\right)=\left(\begin{matrix}n\\0\\\end{matrix}\right)=1\ \ \ \ \ \ \ \ \ \left(\begin{matrix}n\\k\\\end{matrix}\right)=\left(\begin{matrix}n\\n-k\\\end{matrix}\right)\ \ \ \ \ \ \ \ 

מודל 3: בחירה עם חשיבות לסדר ועם החזרה

מספר האפשרויות לבחירה של k עצמים מתוך קבוצה של n עצמים שונים, כאשר הבחירה היא עם חשיבות לסדר ועם החזרה הוא:

n^k

טבלה מסכמת של שלושת המודלים

חישוב הסתברויות במרחב מדגם סימטרי

במרחב מדגם סימטרי הסתברות של מאורע A מחושבת באופן הבא:

P\left(A\right)=\frac{|A|}{|\Omega|}=\frac{רצוי}{מצוי}

מצוי = מספר התוצאות במרחב המדגם

רצוי = מספר התוצאות במאורע המבוקש

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

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

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