יחידה 2: קומבינטוריקה >> 2.1: הגדרות |
קומבינטוריקה
קומבינטוריקה היא דרך מקוצרת לספירה מהירה של מספר אפשרויות. תחום זה כולל מספר מוסכמות כתיבה מקובלות (נוטציות) המתבססות על המושג עצרת: עצרת (factorial) (n!) n!=n*(n-1)*(n-2)*…*1 ב-:EXCEL =FACT(n) 0!=1 1!=1 לדוגמה: 5!=5*4*3*2*1=120
ישנם שלושה מונחים שונים אשר נועדו לבטא ספירת אפשרויות במצבים שונים: |
סדרות
הגדרה: אם חוזרים k פעמים על ניסיון שבו n תוצאות אפשריות, והניסיונות ב"ת אחד בשני, אזי בסה"כ קיימות תוצאות אפשריות בסדרה כולה. בסדרה אנו עוסקים בדגימה עם החזרה: לאחר שבחרנו פריט, בבחירה הבאה ניתן לבחור בו שוב.
דוגמא: בעמודה של טופס טוטו ישנם 14 משחקים (ב"ת). לכל משחק ישנן 3 תוצאות אפשריות (1,2,X). כמה עמודות שונות ניתן למלא?
פתרון:
לשים לב! בסדרות יש חשיבות לסדר!! שתי הסדרות הבאות הינן כל אחת אפשרות בפני עצמה:
ב-EXCEL: =POWER(n,k) |
קומבינציות (צרופים)
הגדרה: בבחירת k פריטים מתוך n, קיימות דרכים שונות לבחירה. מצב זה נקרא "דגימה ללא החזרה" משום שאחרי שבחרנו מקום/פריט לא ניתן לבחור בו שוב.
דוגמא: בחנות מסוימת, במבצע סוף העונה ניתן לקנות 3 חולצות ב-100₪. אם קיימים 8 דגמים, בכמה דרכים יכול לקוח לבחור 3 חולצות שונות?
פתרון: בחירת 3 החולצות: 8 x 7 x 6 אבל מתוך בחירות אלו קיימים סידורים שונים של אותם הפריטים אשר אין להם חשיבות (לא חשוב איזה דגם נבחר ראשון/שני/שלישי) : a,b,c = a,c,b = b,a,c =.. לכן עלינו לחלק במספר הסידורים הפנימיים האפשריים: 3!.
שימו לב: בחירת k פריטים מתוך n זהה לבחירת(n-k) פריטים מתוך n. זאת משום שקביעת מיהם הנבחרים זהה לקביעת מיהם הלא נבחרים (לדוגמה: לבחור 11 שחקני כדורגל מתוך 15 זהה לבחירת 4 השחקנים אשר יישארו על הספסל). מתמטית: , ולכן .
ב-EXCEL =COMBIN(n,k) |
פרמוטציות (תמורות)
הגדרה: פרמוטציות הינן בחירה של מספר פריטים מתוך קבוצה גדולה יותר כאשר ישנה חשיבות לסדר. כלומר, בחירת k פריטים מתוך n כאשר סדר הבחירה חשוב (k יכול להיות = n).
ההבדל בין קומבינציות לפרמוטציות הוא שבקומבינציות הסדר אינו חשוב. כלומר, ניתן להתייחס לפרמוטציות כקומבינציות עם סידור פנימי.
1. המצב המוכר ביותר של פרמוטציות (מקרה פרטי) הינו סידור של n פריטים, קיימות n! דרכים שונות לסידור.
דוגמא: בכמה דרכים ניתן להושיב 4 אנשים סביב שולחן?
פתרון:
הערה: בשולחן עגול קיימות (n-1)! דרכים לסידור מאחר והאדם הראשון קובע את נקודת ההתייחסות- מכיוון שאין פאות שונות לשולחן עגול הרי שיש צורך לקבע נקודת התייחסות. לאחר שנבחרה נקודה זו, המצב הוא כמו של שולחן רגיל.
2. בסידור של k פריטים מתוך n, קיימות דרכים שונות לסידור. דוגמא: בכמה דרכים ניתן להושיב 3 אנשים מתוך 6 אפשריים בשורה?
פתרון:
פרמוטציות ב-EXCEL: =COMBIN(n,k)*FACT(k) |
סיכום קומבינטוריקה
|
|