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

צירופים עם החזרה

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

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

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

פתרון

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

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

דוגמה אפשרית אחת לחלוקת מחיצות היא זו:

כאן בתא השמאלי ביותר כדור אחד, בתא שאחריו שניים, אחר כך שוב אחד, ואז שוב שניים.

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

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

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

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

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

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

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

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

• $\ {n-1+k \choose n-1}={n-1+k \choose k}$.

שימושים

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

1. כפי שכבר ראינו, מספר האפשרויות לחלק $\ k$ כדורים זהים ל-$\ n$ תאים מבלי שיהיו מגבלות על החלוקה הוא $\ {n-1+k \choose k}$.
2. מספר הפתרונות במספרים טבעיים של המשוואה .$\ x_{1}+x_{2}+\dots +x_{n}=k$ הוא $\ {n-1+k \choose k}$.

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