מתמטיקה תיכונית/אלגברה תיכונית/קומבינטוריקה/תמורות/הוכחה:מספר התמורות של n איברים שונים הוא n!

הוכחה:

נניח כי יש לנו $n$ אברים שונים שאנחנו רוצים לסדר בשורה.

נסתכל על המקום הראשון בשורה: ניתן לבחור אליו כל אחד מ־ $n$ האיברים בו ולכן קיימים לו $n$ אפשרויות.
נסתכל במקום השני בשורה: נותרו לנו $n-1$ איברים ולכן ניתן לשבץ במקום השני רק $n-1$ אפשרויות. הרי איבר אחד כבר שובץ במקום הראשון, ולכן אינו יכול להיות בשני מקומות בו־זמנית.
במקום השלישי : נשארו לנו $n-2$ איברים ולכן קיימים רק $n-2$ אפשרויות לשבץ במקום זה.
עבור $k$ איברים יישארו לנו $n-k$ איברים ולכן ניתן לשבץ $n-k+1$ אפשרויות.
במקום האחרון יש רק אפשרות אחת – האבר הבודד שנשאר.

על פי עקרון הכפל והחיבור מספר האפשרויות הכולל לסידור הוא $n(n-1)*\cdots *2*1=n!$ .

עקרון הכפל עריכה

משפט 1: עקרון הכפל

בניסוי שיש בו שני שלבים כך שתוצאת השלב הראשון לא משפיעה על מספר התוצאות האפשריות בשלב השני, מספר התוצאות האפשריות הכולל של הניסוי שווה למכפלת התוצאות האפשריות בשלב הראשון במספר התוצאות האפשריות בשלב השני.

ננסה להבהיר את העקרון על־ידי מספר דוגמאות.

דוגמה 2: מה מספר האפשרויות להרכיב סט עם חמישה זוגות מכנסים ושמונה לחולצות?

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

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

{{{תוכן}}}

דוגמה 4: כמה אפשרויות יש למנות שישה תלמידים לתפקידים של יושב ראש, סגן וגזבר?

נוכל לבצע את חלוקת התפקידים כך:

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

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

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

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

עקרון החיבור עריכה

משפט 2: עקרון החיבור

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

גם כאן נבהיר את העקרון עם מספר דוגמאות.

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

נסתכל על ניסוי בחירת הבגדים כשני ניסויים שונים: באחד בוחרים רק בגדים לבנים, ובשני רק בגדים שחורים. כל אחד מהניסויים הללו הוא בעצמו דו־שלבי – קודם בוחרים מכנסיים ואז בוחרים חולצה. על־פי עקרון הכפל, יש לנו 9 אפשרויות לבחור בגדים שחורים ו־10 אפשרויות לבחור בגדים לבנים, ולכן על־פי עקרון החיבור יש לנו 19 אפשרויות לבחור בגדים בסך הכל.

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

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