מתמטיקה תיכונית/אלגברה תיכונית/קומבינטוריקה/תמורות/סידור של איברים כאשר לא כל האיברים שונים זה מזה

תמורות באיברים זהים

טענה 1: מספר האפשרויות של סידור איברים כאשר לא כל האיברים שונים זה מזה מספר האפשרויות לסדר $n$ איברים בשורה כשמתוכם $n_{1}$ איברים זהים מסוג ראשון, $n_{2}$ איברים זהים מסוג שני,..., $n_{k}$ איברים זהים מסוג $k$ כאשר $n_{1}+n_{2}+...+n_{k}=n$ הוא $p_{n}(n_{,}1,n_{2},n_{3},...n_{k})={\frac {n!}{n_{1}!*n_{2}!*...*n_{k}!}}$

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

דוגמה 1: מה מספר התמורות לסדר שתי אותיות א? נסתכל למשל על מספר הסידורים השונים של האותיות: א', א'. אם שתי האותיות היו שונות זו מזו היינו נעזרים בנוסחת התמורות של $n$ איברים שונים והיינו מקבלים $2!=1*2=2$ אפשרויות. במקרה בו יש לנו שתי אותיות זהות אנו מקבלים אפשרות אחת בלבד : א,א. הרי אין הבדל בין האפשרויות (א', א') ל-(א',א') ולכן התוצאה מצטמצמת לאחת.

דוגמה 2: מה מספר התמורות לסדר את האותיות א', א', ב'? אם ששלושת האותיות היו שונות זו מזו היינו נעזרים בנוסחת התמורות של $n$ איברים שונים והיינו מקבלים $3!=1*2*3=6$ אפשרויות. במקרה בו יש לנו שתי אותיות זהות נקבל את האפשרויות הבאות: אאב אבא באא כלומר קבלנו שוב מחצית מאפשרויות שהינו מקבלים לו האיברים היו שונים זה מזה.

דוגמה 3: מה מספר התמורות לסדר את האותיות א', א', א', ב'? אם ארבעת האותיות היו שונות זו מזו היינו נעזרים בנוסחת התמורות של $n$ איברים שונים והיינו מקבלים $4!=1*2*3*4=24$ אפשרויות. במקרה בו יש לנו שתי אותיות זהות נקבל את האפשרויות הבאות: א, א, א, ב. א, א, ב, א. א, ב, א, א. ב, א, א, א. הפעם לא קבלנו מחצית מהאיברים. מה הקשר בין מספר האיברים הזהים למספר התמורות הכללי?

הקשר בין מספר התמורות של האיברים הזהים למספר התמורות הכללים?

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

אם כן מספר הסידורים הכללי של $n!$ תלוי במספר הסידורים הפנימים של האיברים החוזרים על עצמם.

מה הוא מספר הסידורים הפנימים?

במקרה של האותיות א', א' מספר הסידורים הפנימי היה $\ 2!=2$.

במקרה של האותיות א', א', ב' מספר הסידורים הפנימי היה $\ 2!=1*2=2$

במקרה של האותיות א, א, א', ב', מספר הסידורים הפנימי היה $3!=1*2*3=6$

מאחר שהחישוב הפנימי מציג את מספר האפשרויות החוזרות על עצמן נרצה לחלק בו ממספר האפשרויות הכללי (אם היו לנו שני איברים שחוזרים על עצמם רצינו לחלק בשתי כי קיימת אפשרות שהיא כפולה וכן הלאה). אם כן כאשר יש לנו סידור בשורה של $\ n$ איברים מתוכם $\ k$ זהים זה לזה ואין עוד איברים שזהים זה לזה, נקבל שיש $\ {\frac {n!}{k!}}$ אפשרויות סידור שונות.

מה קורה אם יש לנו יותר מאיבר אחד זהה?

אם יש לנו $\ n$ איברים כך ש-$\ n_{1},n_{2},\dots ,n_{k}$ הם כמות הקבוצות של איברים זהים ב-$n$ (מתקיים $\ n_{1}+n_{2}+\dots +n_{k}=n$) אז יש בסך הכל $\ {\frac {n!}{n_{1}!n_{2}!\cdots n_{k}!}}$ סידורים אפשריים שלהם בשורה.

הנוסחה לסידור איברים שונים בשורה היא למעשה מקרה פרטי של נוסחה זו. אם גודל של קבוצת האיברים הזהים הוא $\ 1$ כלומר כל איבר זהה לעצמו. אז מתקיים $\ n_{1}=n_{2}=\dots =n_{k}=1$ ולכן מספר הסידורים שלהם הוא $\ {\frac {n!}{1\cdot 1\cdots 1}}=n!$, דהינו $n!$ שהיא הנוסחה השל סידור איברים בשורה.

דוגמאות לפתרון בעיות

דוגמה 1

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

1. ללא מגבלה.
2. אם יעל רוצה לשבת ליד דני.
3. אם יעל לא רוצה לשבת ליד דני.
4. אם רוצים שלא יהיו שני בנים שיושבים אחד ליד השני, או שתי בנות שיושבות אחת ליד השניה.

פתרון

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

דוגמה 2

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

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

פתרון

1. אם כל השדרים משדרים אותו מספר שעות, כל אחד משדר בדיוק $\ {\frac {12}{4}}=3$ שעות. ניתן אם כן להסתכל על שיבוץ השדרים כעל סידור בשורה של 4 עצמים (השדרים) שכל אחד מהם מופיע 3 פעמים (בסך הכל 12 שעות שידור). לכן מספר האפשרויות הוא $\ {\frac {12!}{3!3!3!3!}}={\frac {12!}{6^{4}}}=369600$.
2. כאן יש גם כן סידור בשורה של 4 עצמים, אך מספר העותקים מכל עצם שונה (למרות שמספר הכולל הוא עדיין 12). לכן הפעם מספר האפשרויות הוא $\ {\frac {12!}{1!2!4!5!}}={\frac {12!}{1\cdot 2\cdot 24\cdot 120}}={\frac {12!}{5760}}=83160$.
3. מכיוון ששדר הספורט משדר את כל השעות שלו ברצף, ניתן להסתכל עליהן כעל איבר בודד ולא כעל שלושה איברים זהים אך נפרדים. לכן הפעם יש לנו רק 10 עצמים שאנחנו מסדרים - עצם אחד הוא השעות של שדר הספורט, ועוד שלושה עצמים לכל אחד מהשדרים האחרים, שמסמלים את השעות שלו. לכן מספר האפשרויות הוא: $\ {\frac {10!}{1!3!3!3!}}={\frac {10!}{6^{3}}}=16800$.
4. ראשית צריך לגלות כמה שעות משדרים השדרים האחרים. אם כל השדרים האחרים ישדרו שעה אחת, בסך הכל יהיו 9 שעות תפוסות (שעה לכל שדר מהשלושה, ועוד שעתיים לאקטואליה אחריו). הדרך היחידה להגיע ל-12 שעות היא הוספת שעה רצופה אחת לכל אחד מהשדרים. קיבלנו שכל שדר משדר שעתיים רצופות פרט לשדרת האקטואליה, שמשדרת שעתיים אחרי כל אחד מהשדרים האחרים. לכן הדבר היחיד שנותר לעשות הוא לקבוע את הסדר הפנימי אצל השדרים האחרים. מכיוון שיש 3 שדרים, מספר האפשרויות הוא $\ 3!=6$ - סידור רגיל בשורה.

הפרק הקודם: תמורות

תמרוות במעגל ותמורות באיברים זהים תרגילים

הפרק הבא: צירופים