קומבינטוריקה - שאלה פשוטה בספירה בסיסית

[csstud]

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

 

חלוקה של n כדורים שונים ל-k תאים זהים, כאשר אף תא אינו ריק.

 

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

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

סה"כ: (n מעל k) * (k בחזקת n-k).

 

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

[Mr.T]

אתה סופר את חלק מהמצבים כמה פעמים.

נניח שיש שני תאים ו-3 כדורים

נניח אנחנו מסתכלים על החלוקה {1,2} ו-{3}

אפשר להגיע אליה בשתי דרכים לפי הפיתרון שלך:

לבחור את 1 ו-3 בהתחלה (n מעל k) ואז למקם את 2 ביחד עם 1

או לבחור את 2 ו-3 בהתחלה ואז למקם את 1 ביחד עם 2.

 

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

[csstud]

תודה :smile:

 

בהרצאה הראו שתי דרכים:

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

סה"כ: S(n,k) = S(n-1,k-1) + S(n-1,k)*k.

2. פתרו קודם את הבעיה עבור תאים שונים, וחילקו ב-!k כדי לבטל את הסדר.