שאלה עם קומבינטוריקה ונוסחת נסיגה

[גבריאל]

http://i.imgur.com/mYwSOIZ.png

כבר הצלחתי לבנות ולספור ולראות שK1 זה 1, שK2 זה 2, שK3 זה 4, שK4 זה 10, שK5, זה 26, שK6 זה 91 ושK7 זה 242, ואני עדיין לא מצליח לזהות כאן יחס נסיגה עבור Kn.

 

PLEASE HELP!!!

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

[incog]

נסתכל על חלוקה {1,2,..,n} ונסתכל על 1 ועל כל החלוקות , יש כמה אפשרויות:
1) מספר החלוקות שלא מכילות את 1 הוא כמספר החלוקות של k_n-1

2) מספר החלוקות שמכילות את 1 כיחידון הוא שוב כמספר החלוקות של Kֹ_n-1

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

כלומר סה"כ קיבלת את הנוסחא:
K_n=k_n-1+k_n-1+(n-1)k_n-2

[גבריאל]

אתה בטוח שזה נכון? כי אז או שלא הבנתי את השאלה בכלל, או שחישבתי לא נכון את האפשרויות.

 

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

[incog]

אה הבנתי, אז צריך להוריד את האפשרות הראשונה (ש-1 לא נמצא בחלוקה)
ומקבלים:
k_n=k_n-1+(n-1)k_n-2

 

(עכשיו זה מסתדר גם עם הסדרה שלך)

[גבריאל]

תודה, אני אוהב אותך!!!!!   :oops: