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

מתוך ויקיספר, אוסף ספרי הלימוד והמדריכים החופשי.

< מתמטיקה תיכונית | אלגברה תיכונית | קומבינטוריקה(הופנה מהדף אלגברה תיכונית/קומבינטוריקה/תמורות)

תוכן עניינים

1 תמורות

[עריכה] תמורות

[עריכה] עצרת

לפני שנתחיל בלימודי הקומבינטוריקה נכיר ביטוי שימושי שמופיע רבות בפתרון בעיות קומבינטוריות: העצרת.

עצרת מוגדרת רק עבור מספרים טבעיים ( $\ 1,2,3,\dots$ ) ואפס. עבור המספר $\ n$ מסמנים את העצרת שלו בתור $\ n!$ והיא מוגדרת כך: $\ n!=1\cdot 2\cdot 3\cdots n$ . כלומר, כופלים את כל המספרים הטבעיים עד $\ n$ כולל.

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

$\ 1!=1$
$\ 2!=1\cdot 2=2$
$\ 3!=1\cdot 2\cdot 3=6$
$\ 4!=1\cdot 2\cdot 3\cdot 4=24$

מייד אפשר לראות שמתקיימת התכונה הבאה: $\ n!=(n-1)!\cdot n$ לכל $\ n>1$ .

עבור $\ 0$ נוהגים להגדיר $\ 0!=1$ . הגדרה זו קיימת לצרכי נוחות - בהמשך נראה כי הדבר מפשט ביטויים מסויימים.

ההגדרה $\ 0!=1$ אינה שרירותית לחלוטין. על פי ההגדרה הבסיסית של עצרת, $\ 0!$ הוא "מכפלה ריקה", שכן ביטוי זה מסמל את מכפלת כל המספרים הטבעיים הגדולים או שווים ל-1 וקטנים או שווים ל-0, ולא קיים אף מספר כזה. ניתן לצפות כי למכפלה ריקה יהיה ערך נייטרלי לכפל (להבדיל מכפל במספר 0) שכן אם נפרק ביטוי כלשהו לעצמו ולמכפלה ריקה, לא נרצה שערכו ישתנה. הערך הנייטרלי לכפל הוא 1.

[עריכה] תמורות

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

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

אבג
אגב
באג
בגא
גאב
גבא

יש בסך הכל שש אפשרויות שונות.

אם היינו רוצים לסדר רק את א', ב', היינו מקבלים רק שתי אפשרויות:

אב
בא

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

מספר התמורות של $\ n$ איברים שונים הוא $\ n!$ .

נוכיח טענה זו.

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

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

[עריכה] עקרון הכפל ועקרון החיבור

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

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

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

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

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

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

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

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

נציג כעת את העקרון המשלים לעקרון הכפל: עקרון החיבור:

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

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

נניח שיש לנו שמונה מסטיקים וחמישה שוקולדים ואומרים לנו שאנחנו יכולים לבחור ממתק אחד. ניתן להסתכל על הניסוי של בחירת הממתק כשני ניסויים נפרדים, כאשר בניסוי אחד בוחרים מסטיק אחד מבין כל המסטיקים, ובניסוי השני בוחרים שוקולד אחד מבין כל השוקולדים. מספר האפשרויות בניסוי הראשון הוא 8, מספר האפשרויות בניסוי השני הוא 5, ואין תוצאה שהיא משותפת לשני הניסויים (כי באחד בוחרים מסטיקים ובשני שוקולדים) ולכן מספר האפשרויות הכולל הוא 13, סכומם של 5 ו-8.
נניח שאנחנו רוצים לבחור מכנסיים וחולצה בעלי צבע תואם. יש לנו 3 זוגות מכנסיים שחורים ו-2 זוגות מכנסיים לבנים, וכמו כן 3 חולצות שחורות ו-5 חולצות לבנות. נסתכל על ניסוי בחירת הבגדים כשני ניסויים שונים: באחד בוחרים רק בגדים לבנים, ובשני רק בגדים שחורים. כל אחד מהניסויים הללו הוא בעצמו דו שלבי - קודם בוחרים מכנסיים ואז בוחרים חולצה. על פי עקרון הכפל, יש לנו 9 אפשרויות לבחור בגדים שחורים ו-10 אפשרויות לבחור בגדים לבנים, ולכן על פי עקרון החיבור יש לנו 19 אפשרויות לבחור בגדים בסך הכל.
ניתן כעת דוגמה למקרה שבו עקרון החיבור אינו מתקיים: נניח שיעל ודני רוצים לראות טלוויזיה. יעל רוצה לראות את ערוץ הספורט, ערוץ הסרטים וערוץ החדשות, ודני רוצה לראות את ערוץ הסרטים, ערוץ הילדים וערוץ מזג האוויר. כמה אפשרויות יש לבחור ערוץ שלפחות אחד משניהם רוצה לראות? אפשר לחלק את הניסוי לשני ניסויים - באחד אנו בוחרים ערוץ שיעל רוצה לראות ובשני בוחרים ערוץ שדני רוצה לראות. מספר התוצאות האפשריות בכל ניסוי הוא 3 ולכן על פי עקרון החיבור יש 6 תוצאות אפשריות. אולם דבר זה אינו נכון, כי בסך הכל יש 5 ערוצים שדני או יעל רוצים לראות: ספורט, סרטים, חדשות, ילדים ומזג אוויר. הסיבה שעקרון החיבור נכשל היא שתוצאות שני הניסויים, זה של יעל וזה של דני, אינן בהכרח שונות: בשני הניסויים תוצאה אפשרית משותפת היא "ערוץ הסרטים".

[עריכה] דוגמאות לפתרון בעיות

[עריכה] דוגמה 1

כמה מילים שונות (לא בהכרח מילים בעלות משמעות) בעלות שש אותיות, ניתן ליצור מהאותיות א', ב', ג', ד', ה', ו' כאשר משתמשים בכל אות פעם אחת, ותחת המגבלות הבאות:

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

[עריכה] פתרון

מכיוון שאין לנו הגבלות ולא צריך שהמילים תהיינה בעלות משמעות, יש לנו סידור בשורה של 6 אותיות שונות זו מזו, ולכן הפתרון הוא $\ 6!=720$ .
אם המילה חייבת להתחיל באות א' נשים את האות במקום הראשון ונבדוק כמה סידורים אפשריים לשאר המקומות. מכיוון שכל סידור תקין, הבעיה זהה לבעיה של סידור 5 אותיות בשורה - נסדר בשורה את כל האותיות פרט לא' ואז נוסיף את א' בתחילת השורה. לכן הפתרון הוא $\ 5!=120$ .
בצורה ישירה ניתן לפתור את התרגיל כך: למקום הראשון ניתן לבחור רק אחת מתוך 5 אותיות (כי א' פסולה) ולכן יש לנו 5 אפשרויות. כדי לסדר את שאר המקומות אנחנו צריכים לסדר בשורה את 5 האותיות שנותרו ללא מגבלות על הסידור, ולכן יש $\ 5!=120$ אפשרויות לעשות זאת. על פי עקרון הכפל נקבל כי בסה"כ יש לנו $\ 5\cdot 5!=600$ אפשרויות.
נציג כעת פתרון עקיף: נסתמך על כך שידוע הפתרון לסעיפים הקודמים: אם יש 720 אפשרויות סידור באופן כללי, ובדיוק 120 מתוכן הן פסולות כי בהן (ורק בהן) המילה מתחילה בא', מספר האפשרויות שנותר הוא $\ 720-120=600$ . כדאי מאוד לזכור שיטת פתרון זו שכן לעתים קל יותר לחשב את מספר האפשרויות של המקרה המנוגד לזה שאנחנו צריכים למצוא, ולחסר מספר אפשרויות זה ממספר האפשרויות הכולל ללא מגבלות.
יש לנו רק שלוש אותיות אהו"י: האותיות א', ה', ו', ולכן רק בהן עוסק התרגיל. אנחנו מבדילים בין שני ניסויים: זה שבו כל אותיות אהו"י הן בחצי הראשון וזה שבו כולן בחצי השני. על פי עקרון החיבור מספר האפשרויות הכולל הוא סכום האפשרויות בשני המקרים, ומכיוון ששני המקרים סימטריים מספיק למצוא את מספר האפשרויות במקרה אחד ולכפול ב-2.
אם כל אותיות אהו"י הן בחצי הראשון נסדר אותן בסדר כלשהו, ואת שאר האותיות נסדר בחצי השני בסדר כלשהו. מספר הסידורים של החצי הראשון לא משפיע על מספר הסידורים של החצי השני, ולכן על פי עקרון הכפל מספר הסידורים הכולל הוא מספר הסידורים של החצי הראשון כפול מספר הסידורים של החצי השני. סידור של כל אחד מהחצאים הוא סידור של שלוש אותיות בשורה ולכן יש $\ 3!=6$ אפשרויות לסידור כל חצי. לכן בסך הכל יש $\ 6\cdot 6=36$ סידורים, ומכיוון שצריך לכפול תוצאה זו ב-2 נקבל שהתשובה הסופית היא $\ 2\cdot 36=72$ .
אם כל אותיות האהו"י סמוכות זו לזו, נביט עליהן כעל אות בודדת, כאילו "הדבקנו" אותן זו לזו. כעת הבעיה היא סידור של ארבע אותיות: האותיות ב', ג', ד' והאות הנוספת, ה"מודבקת". יש לנו $\ 4!=24$ סידורים אפשריים כאלו.
כעת נבדוק בכמה צורות שונות ניתן לבצע את ה"הדבקה". כל הדבקה תלויה בסידור הפנימי של שלוש אותיות האהו"י שלנו, ולכן יש $\ 3!=6$ אפשרויות שונות. לכן על פי עקרון הכפל הפתרון הוא $\ 6\cdot 24=144$ .
בשל המגבלה שלנו יש לסדר את האותיות לסירוגין: אות אהו"י ואחריה אות שאינה אהו"י, וחוזר חלילה. נפרק את הבעיה שלנו לשני ניסויים שונים: באחד המילה מתחילה באות אהו"י ובשני היא מתחילה באות שאינה אהו"י. כמקודם, בגלל הסימטריה בין המקרים והעובדה שבהכרח אחד משניהם מתקיים מספיק למצוא את מספר האפשרויות לאחד מהם ולכפול ב-2.
נניח שהמילה מתחילה באות אהו"י. נסדר קודם כל את אותיות האהו"י בשורה. לשם כך יש לנו $\ 3!=6$ אפשרויות. אחר כך נסדר את האותיות שאינן אהו"י בשורה, גם כן $\ 3!=6$ אפשרויות. כעת נבנה את המילה שלנו כך: נשים את אות האהו"י שבמקום הראשון ברשימה שלה, ואחריה את האות שאינה אהו"י שבמקום הראשון ברשימה שלה. אחר כך נשים את אות האהו"י שבמקום השני ברשימה שלה, וכן הלאה. נקבל מילה שבה מופיעות לסירוגין אותיות אהו"י וכאלו שאינן אהו"י.
מכיוון שהשלב של בניית המילה משתי הרשימות מניב תוצאה אחת בלבד, מספר הפתרונות הכולל, על פי עקרון הכפל, הוא מכפלת האפשרויות ליצירת כל אחת מהרשימות הקצרות, כלומר $\ 6\cdot 6=36$ .

[עריכה] דוגמה 2

נתונות הספרות 0,1,2,3,4,5. מצא כמה מספרים ניתן ליצור תוך שימוש בכולן:

ללא מגבלות.
מספרים שמתחלקים ב-5.
מספרים זוגיים שגדולים מ-300,000.

[עריכה] פתרון

למרות שאין מגבלות מיוחדות על המספרים, מספר ש-0 הוא הספרה השמאלית ביותר בו איננו חוקי, ולכן למקום השמאלי ביותר יש לנו בחירה של אחת מתוך 5 ספרות, ועבור שאר 5 המקומות אנחנו משתמשים בנוסחה הרגילה לסידור בשורה. נקבל $\ 5\cdot 5!=5\cdot 120=600$ מספרים אפשריים.
המגבלה של הסעיף הקודם נשארת, וכעת אנחנו חייבים לוודא שהמספר שאנו יוצרים יתחלק ב-5. ידוע כי מספר מתחלק ב-5 אך ורק כאשר הספרה הימנית ביותר בו היא 0 או 5. לכן נפריד בין שני המקרים הללו.
אם בחרנו את 0 בתור הספרה הימנית ביותר, עבור שאר המקומות אנחנו יכולים לבחור מספרים בצורה חופשית ולכן זהו סידור רגיל בשורה ויש $\ 5!=120$ אפשרויות. לעומת זאת, אם בחרנו את 5 בתור הספרה הימנית ביותר צריך לוודא ש-0 לא תהיה הספרה השמאלית ביותר ולכן נפעל בצורה דומה לזו של סעיף א': נבחר אחת מארבע הספרות הנותרות (אלו שאינן 0 או 5) ונשים אותה במקום השמאלי ביותר, ואת יתר הספרות נסדר בשורה. נקבל $\ 4\cdot 4!=4\cdot 24=96$ אפשרויות.
כעת נשתמש בעקרון החיבור (כי מספר יכול שספרתו הימנית ביותר תהיה 0 או 5, אך לא שניהם יחד) ונקבל בסך הכל $\ 120+96=216$ אפשרויות.
כדי שהמספר שלנו יהיה גדול מ-300,000 עלינו לבחור בתור הספרה השמאלית ביותר אחת משלוש הספרות 3,4,5. כדי שהמספר יהיה זוגי עלינו לבחור בתור הספרה הימנית ביותר אחת מהספרות 0,2,4. נפריד בין המקרים על פי הספרה השמאלית ביותר.
אם הספרה השמאלית ביותר היא 3, יש לנו 3 אפשרויות לבחירת הספרה הימנית ביותר, ואחר כך נסדר את 4 הספרות הנותרות בשורה. נקבל $\ 3\cdot 4!=3\cdot 24=72$ אפשרויות. כאשר נבחר בתור הספרה השמאלית ביותר את 5 נקבל את אותה תוצאה בדיוק, מאותם שיקולים.
לעומת זאת, אם נבחר את 4 בתור הספרה השמאלית ביותר לא ניתן לבחור אותו גם בתור הספרה הימנית ביותר, ולכן אנחנו חייבים לבחור אותה מתוך 2 ספרות (0,2) ולכן מספר האפשרויות הפעם יהיה $\ 2\cdot 4!=48$ .
כעת נשתמש בעקרון החיבור ונקבל שבסך הכל יש $\ 72+72+48=192$ מספרים שונים.