שאלה ברקורסיה

[ivg]

שאלה ברקורסיה

מפזרים n כדורים זהים ב- k תאים שונים. נסמן ב- (f(n,k את מספר האפשרויות לפיזור הכדורים בתאים כך שכל תא יכיל לכל היותר 3 כדורים ולפחות 2 כדורים. מצא נוסחה רקורסיבית בעבור (f(n,k. אשמח אם תעזרו לי לפתור את השאלה הזו. תודה מראש!

 

[ש ב ו ז]

רמז בפנים.

נסה לחשוב על זה כך.כל שלב מורכב מ: קודם כל נפזר 2 כדורים בM מתוך K תאים (נתייחס ל2 כדורים כעל כדור אחד). ואז נפזר n-2m כדורים (הנותרים) בין M התאים (כל פעם כדור אחד). מה האפשרויות לכל שלב?

 

[KO74]

ניסיון

f(n,k)=f(n-2,k-1)+f(n-3,k-1) זה הרעיון, יכול להיות שצריך להוסיף +1 בסוף, לא סגור לגבי זה

 

[ivg]

תשובתך נכונה, אשמח אם תסביר כיצד

הגעת לפיתרון.

 

[gil levi]

את מספר האפשרויות לפזר

n כדורים זהים ב k תאים אפשר לקבל באופן הבא: נתבונן בתא הראשון ונחלק למקרים: מקרה 1: נזרוק לתא הראשון שני כדורים ועתה נותר לחלק n-2 כדורים ל k-1 תאים - ולזה יש f(n-2,k-1) zz אפשרויות. מקרה 2: נזרוק לתא הראשון שלושה כדורים ועתה נותר לחלק n-3 כדורים ל k-1 תאים - ולזה יש f(n-2,k-1)zzz אפשרויות. ובסך הכל:f(n,k)=f(n-2,k-1)+f(n-3,k-1) zzz .