ברוכים הבאים ליחידת הלימוד "עקרונות ספירה בסיסיים"! ביחידה זו נצלול לעולם הקומבינטוריקה, ענף מרכזי במתמטיקה בדידה החיוני למדעי המחשב, סטטיסטיקה ותחומים רבים אחרים. נלמד כיצד לספור באופן שיטתי את מספר האפשרויות לסידור או בחירה של עצמים, תוך הבחנה קריטית בין מצבים שבהם הסדר חשוב לבין מצבים שבהם הוא אינו חשוב, ובין מצבים שבהם ניתן לחזור על עצמים לבין מצבים שבהם לא. הבנה מעמיקה של עקרונות אלו תהווה בסיס איתן לפתרון בעיות ספירה מורכבות יותר.
עקרונות ספירה יסודיים
לפני שנעמיק בסידורים ובחירות, נכיר שני עקרונות בסיסיים המהווים את אבני הבניין של כל בעיית ספירה.
עקרונות אלו משמשים אותנו לפירוק בעיות ספירה מורכבות לרכיבים פשוטים יותר.
הבחנה בין סידורים לבחירות
ההבחנה המרכזית בקומבינטוריקה היא בין סידור (פרמוטציה) לבחירה (קומבינציה). הבנה נכונה של הבדל זה היא המפתח לבחירת הנוסחה המתאימה.
בנוסף, עלינו לשקול האם מותר לחזור על עצמים שנבחרו:
ארבעת המקרים המרכזיים בספירה
שילוב ההבחנות לעיל מוביל לארבעה תרחישי ספירה בסיסיים, שלכל אחד מהם נוסחה ייחודית. חשוב להבין את ההיגיון מאחורי כל נוסחה.
סידורים בלי חזרות
בחירת k עצמים מתוך n עצמים שונים, כאשר הסדר חשוב ואין חזרות. מספר האפשרויות הוא P(n, k) = n! / (n-k)!. מקרה פרטי: סידור כל n העצמים הוא n!.
סידורים עם חזרות
בחירת k עצמים מתוך n עצמים שונים, כאשר הסדר חשוב ומותרות חזרות. מספר האפשרויות הוא nk. לדוגמה, מספר הסיסמאות באורך k מתוך n תווים אפשריים.
בחירות בלי חזרות
בחירת k עצמים מתוך n עצמים שונים, כאשר הסדר אינו חשוב ואין חזרות. מספר האפשרויות הוא C(n, k) = n! / (k! * (n-k)!), המכונה גם "מקדם בינומי" או n choose k.
בחירות עם חזרות
בחירת k עצמים מתוך n עצמים שונים, כאשר הסדר אינו חשוב ומותרות חזרות. מספר האפשרויות הוא C(n + k - 1, k). נוסחה זו ידועה גם כ"כוכבים ומחיצות" (Stars and Bars).
שאלות לדיון
- כמה מספרים בני 4 ספרות ניתן ליצור באמצעות הספרות {1, 2, 3, 4, 5} אם: א. מותרות חזרות? ב. אסורות חזרות?
- ועדת סטודנטים צריכה לבחור 3 נציגים מתוך 10 מועמדים. כמה דרכים שונות יש לבחור את הוועדה?
- בכמה דרכים ניתן לחלק 7 כדורים זהים ל-3 תאים שונים? (רמז: חשבו על כוכבים ומחיצות).
- הסבירו במילים שלכם מדוע הנוסחה לסידורים בלי חזרות (P(n, k)) גדולה יותר מהנוסחה לבחירות בלי חזרות (C(n, k)) עבור אותם n ו-k.
נקודות לתשובת מודל
- לגבי מספרים בני 4 ספרות:
- א. מותרות חזרות: כל ספרה נבחרת מ-5 אפשרויות באופן בלתי תלוי. לכן, 54 (סידורים עם חזרות).
- ב. אסורות חזרות: הספרה הראשונה מ-5, השנייה מ-4, השלישית מ-3, הרביעית מ-2. לכן, P(5, 4) = 5! / (5-4)! = 5 * 4 * 3 * 2 (סידורים בלי חזרות).
- לגבי ועדת סטודנטים: הסדר אינו חשוב (קבוצת נציגים), ואין חזרות (כל סטודנט נבחר פעם אחת). לכן, C(10, 3) (בחירות בלי חזרות).
- לגבי חלוקת כדורים לתאים: הכדורים זהים (הסדר לא משנה), וניתן לשים מספר כדורים באותו תא (חזרות). זוהי בעיית "כוכבים ומחיצות", ולכן C(7 + 3 - 1, 3 - 1) = C(9, 2) או C(9, 7) (בחירות עם חזרות).
- ההבדל בין P(n, k) ל-C(n, k): הנוסחה לסידורים בלי חזרות כוללת את כל הסידורים האפשריים של k עצמים שנבחרו. הנוסחה לבחירות בלי חזרות "מבטלת" את חשיבות הסדר על ידי חלוקה במספר הסידורים הפנימיים של k העצמים שנבחרו (k!). כלומר, כל בחירה של k עצמים יכולה להיות מסודרת ב-k! דרכים שונות, ו-C(n, k) סופר כל קבוצה כזו פעם אחת בלבד.