פתרונות נבחרים לשיעורי הבית

תרגיל מס' 10

1.	מצא ביטוי סגור עבור הסדרות הבאות המוגדרות ברקורסיה:
ב.	. תנאי התחלה: .
תהי F הפונקציה שיוצרת את הסדרה . אזי לכל x בתחום ההתכנסות:

נציב x = 0   ונקבל  A+B+C = 0.
נציב  ונקבל , כלומר B = -1.
נציב  x = 1  ונקבל  3A=-3, כלומר  A = -1. מכאן  C = 3.
לכן . פונקציה זאת יוצרת את הסדרה .

2.	רשום יחס רקורסיה ותנאי התחלה עבור מספר המילים בנות n אותיות מהא"ב A, B, C שלא מופיעים בהן הרצפים:
א.	AA
פתרון: המילים החוקיות באורך n שמתחילות באות B הן מילים מהצורה: התו B ואחריו מילה חוקית באורך n -1. המילים החוקיות באורך n שמתחילות באות C הן מילים מהצורה: התו C ואחריו מילה חוקית באורך n -1. המילים החוקיות באורך n שמתחילות באות A הן מילים מהצורה: התוים AB ואחריהם מחרוזת חוקית באורך
n-2 או התוים AC ואחריהם מחרוזת חוקית באורך n-2. לכן נוסחת הנסיגה היא: . תנאי התחלה: .
ב.	AB , BC
פתרון: למילה חוקית באורך n יש שלוש אפשרויות. היא יכולה להתחיל ב – C, לכך יש an-1 אפשרויות. היא יכולה להתחיל ב – B, אבל לא ב – BC. לכך יש  אפשרויות. האפשרות האחרונה היא שהיא מתחילה ב – A, ואחריה מילה חוקית שאינה מתחילה ב – B. מספר המילים החוקיות באורך n-1 שמתחילות ב – B הוא . לפיכך מספר המילים החוקיות באורך n שמתחילות ב – A הוא . אם נסכם את האפשרויות נקבל: . תנאי התחלה הם: .

3.	מצא נוסחת רקורסיה עבור מספר הדרכים לרצף מלבן בגודל  ע"י מרצפות בגודל: .
פתרון: נסמן ב – an את מספר הריצופים האפשריים למלבן בגודל . כל ריצוף ניתן להתחיל באחת משתי הדרכים הבאות: 

לכן נוסחת הרקורסיה היא . תנאי התחלה: .

5.    מבין המספרים , כמה אינם מתחלקים ב – 7, אבל מתחלקים ב – 3 או
ב – 5?
פתרון: נסמן ב – S את קבוצת המספרים שמתחלקים ב – 3 או ב – 5. .
נסמן ב -  את קבוצת המספרים שמתחלקים ב – 3 וב – 7. נסמן ב -  את קבוצת המספרים שמתחלקים ב – 5 וב – 7. ברצוננו לחשב .     ולכן . לפיכך הפתרון הוא: .

6.	בכמה תמורות של האותיות A,B,C,D,E,F,G,H   לא מופיעות המחרוזות הבאות:
א.	AB, DE, EF
פתרון: תהי  קבוצת התמורות בהן מופיע AB. תהי  קבוצת התמורות בהן מופיע DE. תהי  קבוצת התמורות בהן מופיע EF. . . . לכן הפתרון הוא: .

ב.	ABC, CDE, DEF
             פתרון: תהי  קבוצת התמורות בהן מופיע ABC. תהי  קבוצת התמורות בהן מופיע CDE            . תהי  קבוצת התמורות בהן מופיע DEF. .     
            . . לכן הפתרון הוא:   
              .

7.
א.	בכמה דרכים ניתן לחלק 50 כדורים זהים לשלושה תאים כך שבתא הראשון יהיו פחות מ – 10 כדורים, בשני פחות מ – 20 ובשלישי פחות מ – 30?
פתרון: נסמן ב – S את קבוצת החלוקות של 50 כדורים ל – 3 תאים. נסמן ב –  את קבוצת החלוקות של 50 כדורים ל – 3 תאים כך שבתא 1 לפחות 10 כדורים. נסמן ב –  את קבוצת החלוקות של 50 כדורים ל – 3 תאים כך שבתא 2 לפחות 20 כדורים. נסמן ב –  את קבוצת החלוקות של 50 כדורים ל – 3 תאים כך שבתא 3 לפחות 30 כדורים.
, ,,, , ,, . לכן הפתרון הוא: .

ב.	בכמה דרכים ניתן לחלק 50 כדורים שונים לשלושה תאים כך שאף תא לא יהיה ריק?
פתרון: .