מתמטיקה תיכונית/אלגברה תיכונית/קומבינטוריקה/תמורות/עקרון הכפל

משפט 1: עקרון הכפל מספר התוצאות האפשרויות של ניסוי בעל מספר של שלבים שווה למכפלת התוצאות שהתקבלה בכל שלב.

עקרון הכפל בעקרון מוגבר לניסוי דו שלבי, אולם אין בעיה להכליל אותו באינדוקציה לניסוי בעל מספר שלבים סופי כלשהו, אם אנחנו דורשים שתוצאה של אף אחד מהשלבים לא תשפיע על מספר התוצאות האפשריות בשלב מתקדם יותר. כך אנחנו גם משתמשים בעקרון הכפל בהוכחה שלנו שמספר התמורות על $n$ אברים הוא $n!$ . הראינו שסידור האברים בשורה הוא ניסוי בעל $n$ שלבים, כך שמספר התוצאות האפשריות בשלב ה־$k$ הוא תמיד $n-k+1$ בלי תלות בתוצאות של השלבים שלפניו, ולכן מספר התוצאות האפשריות הכולל הוא מכפלת מספר התוצאות האפשריות בכל שלב בניסוי.

דוגמאות

דוגמה 2: מה מספר האפשרויות להרכיב סט עם חמישה זוגות מכנסים ושמונה לחולצות? ניתן להסתכל על בחירת הלבוש בתור "ניסוי" שבו השלב הראשון הוא בחירת המכנסיים והשלב השני הוא בחירת החולצה. זוג המכנסיים שנבחר לא ישפיע על החולצה שנוכל לבחור, ולכן לכל אחד מ־5 זוגות המכנסיים נוכל לבחור אחת מ-8 החולצות. לכן מספר האפשרויות הכולל של צירופי בגדים שאנו יכולים לבחור הוא $8*5=40$.

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

דוגמה 4: כמה אפשרויות יש למנות שלושה תלמידים לתפקידים של יושב ראש, סגן וגזבר? נוכל לבצע את חלוקת התפקידים כך: בשלב הראשון נבחר את יושב־הראש מבין שלושת התלמידים, ובשלב הבא נבחר את הסגן מבין שני התלמידים הנותרים, ואז תפקיד הגזבר יוותר לתלמיד השלישי. גם כאן אנחנו מבצעים ניסוי דו־שלבי: בשלב הראשון יש לנו 3 אפשרויות ובשלב השני 2 בלבד. גם כאן התוצאות של השלב השני תלויות בתוצאות של השלב הראשון (אם בחרנו את יעל כיושבת ראש היא לא יכולה להיבחר בשלב השני כסגן, אך אם דני נבחר כיושב־ראש היא כן יכולה להיבחר כסגן), אך מספר האפשרויות של השלב השני תמיד יהיה שתים. נשים לב לדמיון שבין הדוגמה השלישית ובין הבעיה של מציאת תמורות. במקום לבחור יושב־ראש, סגן וגזבר היינו יכולים לסדר את התלמידים בשורה ולחלק את התפקידים על־פי המקום שלהם בשורה. כך היינו מבצעים צמצום של הבעיה לבעיה שאותה אנחנו כבר יודעים לפתור. שיטת צמצום זו שימושית מאוד בפתרון בעיות בקומבינטוריקה.