בעיה בכללי נסיגה:

[tom1992]

בעיה בכללי נסיגה:

כיצד להגדיר את כלל הנסיגה an - מס' הדרכים לחלק n כדורים ממוספרים מ-1 עד n
ל-3 תאים, כך שבתא הראשון אין שני כדורים עם מספרים עוקבים ?

 

[עריסטו]

נעשה כך

a(0)=1
a(1)=3
n>1: a=2a(n-2)+2a(n-1)
הסבר:
בכל חלוקה חוקית של n כדורים, או שכדור n נמצא בתא הראשון או שלא.
כדי לקבל חלוקה חוקית שבה כדור n נמצא בתא הראשון, לוקחים חלוקה חוקית של n-2 כדורים, שמים את כדור n-1 בתא שאינו הראשון, ושמים את כדור n בתא הראשון.
כדי לקבל חלוקה חוקית שבה כדור n לא נמצא בתא הראשון, לוקחים חלוקה חוקית של n-1 כדורים ושמים את כדור n בתא שאינו הראשון.