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

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

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

קפיצה אל: ניווט, חיפוש

תוכן עניינים

1 תמורות במעגל
2 תמורות באיברים זהים
3 דוגמאות לפתרון בעיות

[עריכה] תמורות במעגל

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

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

נראה כעת את הנוסחה הכללית:

סידור של $\ n$ איברים שונים במעגל ניתן להיעשות ב- $\ (n-1)!$ דרכים שונות.

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

אבג, בגא, גאב.

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

נשים לב שמבין הסידורים הזהים, קיים אחד בלבד שבו א' במקום הראשון, אחד שבו א' במקום השני וכן הלאה. ניתן לחשוב על א' כעל "נקודת ייחוס" בשורה שממנה אנו מתחילים לסדר את שאר האיברים, ואם הגענו לסוף השורה אנו חוזרים לתחילתה וממשיכים לסדר איברים עד שאנו מגיעים שוב אל א'.

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

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

[עריכה] תמורות באיברים זהים

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

נסתכל למשל על מספר הסידורים השונים של האותיות א', א', ב'. אלו הן שלוש אותיות ואם כולן היו שונות זו מזו היו לנו 6 סידורים. כעת יש לנו 3 סידורים בלבד:

אאב, אבא, באא.

ננסה להבין מדוע קיבלנו 3 סידורים.

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

א1א2ב, א2א1ב.

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

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

אם יש לנו $\ n$ איברים כך ש- $\ n_1,n_2,\dots,n_k$ הם הגדלים של הקבוצות של איברים זהים מתוכם (מתקיים $\ 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!$ , ולכן קיבלנו הכללה של הנוסחה המקורית לתמורות.

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

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

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

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

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

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

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

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

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

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

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