מחשבון קומבינטוריקה

עצרת, חליפות וצירופים

עצרת (n!) = מכפלת כל המספרים מ-1 עד n. חליפות P(n,r) = מספר הדרכים לסדר r פריטים מתוך n כשהסדר חשוב. צירופים C(n,r) = מספר הדרכים לבחור r פריטים כשהסדר לא חשוב. בלוטו 6 מתוך 37 = צירופים.

מתי הסדר חשוב ומתי לא?

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

למה המספרים גדלים כל כך מהר?

עצרת היא אחת הפונקציות הצומחות המהירות במתמטיקה: 5! = 120, אבל 10! כבר מעל שלושה מיליון, ו-20! הוא מספר בן 19 ספרות. לכן בבעיות ספירה אפילו קבוצות קטנות מייצרות מספרי אפשרויות עצומים. זו גם הסיבה שהסיכוי לזכות בלוטו (1 מתוך 2.3 מיליון) כה נמוך — מספר הצירופים האפשריים פשוט אדיר.

שאלות נפוצות