מושגים בפסיכומטרי: קומבינטוריקה: עקרון הכפל, סידורים ובחירות

עקרון הכפל

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

מפרקים לשלבים וכופלים

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

כופלים ולא מחברים, כי כל אפשרות בשלב הראשון מתחברת לכל אחת מהאפשרויות בשלב השני. עם 3 חולצות ו-2 זוגות מכנסיים, כל חולצה יוצרת 2 צירופים, ולכן יש $3\cdot 2=6$ צירופים — ולא $3+2=5$.

דוגמה: מרכיבים כריך. בוחרים סוג לחם אחד מתוך 3, מילוי אחד מתוך 5 ורוטב אחד מתוך 4. יש כאן שלושה שלבים, ולכן מספר הכריכים השונים הוא $3\cdot 5\cdot 4=60$.

בחירה עם חזרה

כשמותר לבחור את אותו דבר שוב, מספר האפשרויות זהה בכל שלב. דוגמה: מטילים מטבע 4 פעמים. בכל הטלה יש 2 תוצאות, ולכן יש $2\cdot 2\cdot 2\cdot 2=16$ רצפים שונים של תוצאות. באותו אופן, קוד בן 3 תווים שבו כל תו הוא אחת מ-5 אותיות, ומותר לחזור על אות, יכול להיכתב ב-$5\cdot 5\cdot 5=125$ דרכים.

בחירות שתלויות זו בזו

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

אסור לבחור את אותו דבר פעמיים

דוגמה: בתחרות משתתפים 7 מתמודדים, ומחלקים מקום ראשון, מקום שני ומקום שלישי. מתמודד אחד לא יכול לזכות ביותר ממקום אחד. למקום הראשון יש 7 אפשרויות. למקום השני נשארו 6 מתמודדים, כי אחד כבר נבחר. למקום השלישי נשארו 5. לכן יש $7\cdot 6\cdot 5=210$ דרכים לחלק את שלושת המקומות.

אסור ששתי בחירות סמוכות יהיו זהות

דוגמה: צובעים 5 עמודים העומדים בשורה, ולכל עמוד בוחרים אחד מ-4 צבעים. אסור ששני עמודים שכנים יהיו באותו צבע. לעמוד הראשון יש 4 אפשרויות. לכל עמוד שאחריו יש 3 אפשרויות: כל הצבעים חוץ מהצבע של העמוד שלפניו. צבע שכבר הופיע, אבל לא בעמוד הסמוך, מותר שוב. לכן יש $4\cdot 3\cdot 3\cdot 3\cdot 3=324$ צביעות.

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

סידור בשורה ועצרת

סידור של כמה פריטים שונים בשורה הוא מקרה מיוחד של בחירה בלי חזרה: בוחרים מי יעמוד במקום הראשון, מי בשני, וכן הלאה, עד שכל הפריטים סודרו. ל-4 אנשים יש 4 אפשרויות למקום הראשון, 3 לשני, 2 לשלישי ואפשרות אחת לרביעי, כלומר $4\cdot 3\cdot 2\cdot 1=24$ סידורים.

עצרת

למכפלה הזאת יש שם וסימון: $n!$ (קוראים ״n עצרת״) היא המכפלה של כל המספרים השלמים מ-1 עד n. לכן מספר הסידורים של n פריטים שונים בשורה הוא $n!$. כדאי להכיר את הערכים הראשונים: $3!=6$, $4!=24$, $5!=120$ ו-$6!=720$. הערכים גדלים מהר מאוד, ולכן כשהמספרים גדולים התשובות מופיעות לרוב כעצרת ולא כמספר מחושב.

צמצום עצרות

כל עצרת מכילה את העצרת שלפניה: $8!=8\cdot 7!$. לכן בחילוק של עצרות לא מחשבים את המספרים עד הסוף אלא מצמצמים: $\frac{8!}{6!}=8\cdot 7=56$.

סידור עם מגבלה

דוגמה: בכמה דרכים אפשר לסדר 6 ספרים שונים על מדף, כך ששני ספרים מסוימים יעמדו זה ליד זה? מצמידים את שני הספרים ומתייחסים אליהם כאל פריט אחד. עכשיו מסדרים 5 פריטים, ויש לכך $5!=120$ דרכים. בתוך הזוג אפשר להחליף את סדר שני הספרים, ולכן כופלים ב-2: $120\cdot 2=240$ סידורים.

כשהסדר לא חשוב

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

זוגות: מחלקים ב-2

כל קשר בין שני פריטים — לחיצת יד, משחק בין שתי קבוצות, קו בין שתי נקודות, כביש בין שתי ערים — הוא אותו קשר משני הכיוונים, ולכן נספר פעם אחת. דוגמה: בטורניר משתתפות 6 קבוצות, וכל קבוצה משחקת פעם אחת נגד כל אחת מהאחרות. כמה משחקים יש? לקבוצה הראשונה במשחק יש 6 אפשרויות ולשנייה 5, כלומר $6\cdot 5=30$. אבל כך כל משחק נספר פעמיים — פעם כ״א נגד ב״ ופעם כ״ב נגד א״. לכן מחלקים ב-2 ומקבלים $\frac{6\cdot 5}{2}=15$ משחקים. באופן כללי, מספר הזוגות שאפשר ליצור מתוך n פריטים הוא $\frac{n(n-1)}{2}$.

קבוצה של שלושה או יותר

דוגמה: בוחרים 3 נציגים מתוך 7 תלמידים, בלי תפקידים. אילו היו לנציגים תפקידים שונים, היו $7\cdot 6\cdot 5=210$ אפשרויות. אבל בספירה הזאת כל שלישייה נספרה $3!=6$ פעמים, פעם לכל סדר של שלושת חבריה. לכן יש $\frac{210}{6}=35$ דרכים לבחור את הנציגים.

ספירה ישירה כשהמספרים קטנים

כשיש מעט אפשרויות, לעיתים מהיר ובטוח יותר לרשום את כולן באופן מסודר מאשר לחפש נוסחה. זה נכון במיוחד כשיש מגבלה שקשה לתרגם לכפל. דוגמה: שלושה אנשים, א, ב ו-ג, יושבים בשלושה כיסאות צמודים בשורה, ו-א ו-ב חייבים לשבת זה ליד זה. רושמים את כל $3!=6$ הסידורים: אבג, אגב, באג, בגא, גאב, גבא. ב-4 מהם א ו-ב יושבים זה ליד זה: אבג, באג, גאב וגבא. אותה תשובה מתקבלת בשיטת ההצמדה: הזוג ו-ג הם 2 פריטים, ובתוך הזוג יש 2 סדרים, כלומר $2!\cdot 2=4$. כשרשימה ושיטה נותנות אותה תוצאה, אפשר לסמוך על התשובה.

קודים ומספרים

בשאלות על מספרים ועל קודים כל ספרה היא שלב נפרד בעקרון הכפל. יש 10 ספרות, מ-0 עד 9, ובכל מקום בודקים כמה מהן מותרות.

ההבדל בין מספר לקוד

מספר אינו יכול להתחיל ב-0: הרצף 032 אינו מספר תלת-ספרתי. לכן לספרת המאות של מספר תלת-ספרתי יש רק 9 אפשרויות, 1 עד 9. קוד, לעומת זאת, יכול להתחיל ב-0, ולכן בקוד כל מקום פתוח לכל 10 הספרות. יש $10\cdot 10\cdot 10=1000$ קודים בני 3 ספרות, אבל רק $9\cdot 10\cdot 10=900$ מספרים תלת-ספרתיים.

מספר זוגי או אי-זוגי

דוגמה: כמה מספרים תלת-ספרתיים זוגיים יש? לספרת המאות יש 9 אפשרויות (לא 0). לספרת העשרות יש 10 אפשרויות. ספרת האחדות קובעת אם המספר זוגי, ולכן מותרות בה רק 0, 2, 4, 6 ו-8 — 5 אפשרויות. בסך הכול יש $9\cdot 10\cdot 5=450$ מספרים. בדיקה: בין 100 ל-999 יש 900 מספרים, ובדיוק חצי מהם זוגיים. גם מספרים אי-זוגיים יש 450, כי גם לספרת אחדות אי-זוגית יש 5 אפשרויות.

ספרות שונות: מתחילים מהמקום המוגבל

כשהספרות חייבות להיות שונות זו מזו, מספר האפשרויות קטן משלב לשלב, ולכן בוחרים קודם את המקום שיש עליו מגבלה. דוגמה: כמה מספרים בני 4 ספרות שונות יש? לספרת האלפים יש 9 אפשרויות (1 עד 9). לספרה הבאה יש 9 אפשרויות: עכשיו גם 0 מותר, אבל הספרה שכבר נבחרה אסורה. לספרה השלישית יש 8 אפשרויות, ולרביעית 7. בסך הכול $9\cdot 9\cdot 8\cdot 7=4536$ מספרים. לעומת זאת, קוד בן 4 ספרות שונות יכול להתחיל ב-0, ולכן יש $10\cdot 9\cdot 8\cdot 7=5040$ קודים כאלה.