יחידה 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)


סיכום קומבינטוריקה

 

 

► חזור                    המשך ◄