קומבינטוריקה — מתי הסדר חשוב ומתי לא

שאלה אחת מכריעה הכל

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

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

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

שלושת המקרים על אותה קבוצה

נניח שיש 5 אנשים, ונראה מה מקבלים בכל אחד משלושת המקרים.

סידור כל החמישה בשורה — תמורות. יש 5 אפשרויות למקום הראשון, 4 לשני, 3 לשלישי, 2 לרביעי ואחת לאחרון. מכפילים: 5 כפול 4 כפול 3 כפול 2 כפול 1 שווה 120.

בחירת 3 מתוך החמישה כשהסדר משנה — חליפות. 5 אפשרויות לתפקיד הראשון, 4 לשני, 3 לשלישי: 5 כפול 4 כפול 3 שווה 60.

בחירת 3 מתוך החמישה כשהסדר לא משנה — צירופים. לוקחים את 60 מהמקרה הקודם ומחלקים במספר הסידורים של שלושה אנשים, שהוא 3 כפול 2 כפול 1, כלומר 6. מקבלים 60 חלקי 6 שווה 10.

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

כלל הכפל וכלל החיבור

כלל הכפל: כששלב אחד בא אחרי השני, מכפילים. תפריט עם 3 מנות ראשונות ו-4 עיקריות נותן 12 ארוחות אפשריות.

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

ההבדל בין "וגם" לבין "או" הוא ההבדל בין כפל לחיבור, וזה גם ההבדל בין תשובה נכונה לשגויה בשאלה מורכבת. שווה לסמן בשאלה את המילים האלה לפני שמתחילים לחשב.

שאלות עם תנאי

הרבה שאלות מוסיפות הגבלה — למשל שאדם מסוים חייב להיכלל, או ששני אנשים לא יכולים לשבת יחד.

כשמישהו חייב להיכלל: קובעים אותו מראש וסופרים רק את השאר. בחירת ועדה של 3 מתוך 5 כשדן חייב להיות בפנים היא בחירת 2 מתוך ה-4 הנותרים, כלומר 6 אפשרויות.

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

שאלות נפוצות

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

למה אפס עצרת שווה 1 ולא 0? כי יש בדיוק דרך אחת לסדר קבוצה ריקה — לא לעשות כלום. זה נראה כמו הגדרה שרירותית אבל הוא מה שמאפשר לנוסחאות לעבוד בקצוות בלי מקרים מיוחדים.