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

תרגיל מס' 11

1.    הביאו נימוקים קומבינטורים מדוע  מספר שלם ומדוע  גם כן מספר שלם.
     פתרון: מספר האפשרויות לחלק  2n אנשים ל – 2 קבוצות שבכל אחת n אנשים, כאשר יש      
   חשיבות לסדר בין הקבוצות, הוא . כאשר אין חשיבות לסדר בין הקבוצות, המספר הוא .

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

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

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

3.	תהינה A ו B קבוצות. |A|=n כאשר n>3 טבעי. מה עוצמת הקבוצה  אם בקבוצה B יש:
א.	איבר אחד
פתרון: הפונקציה האחת והיחידה היא גם על.
ב.	שני איברים
פתרון: יש  פונקציות ב - . כולן על פרט לשתיים: הפונקציה שמתאימה את כל האיברים ב – A לאיבר הראשון של B, והפונקציה שמתאימה את כל האיברים ב – A לאיבר השני של B. לכן התשובה: .
ג.	n איברים
פתרון: כמספר הפרמוטציות בגודל n, כלומר n!.
ד.	n-1 איברים
פתרון: על מנת שהפונקציה תהיה על, חייבים להיות בדיוק שני איברים ב – A שתמונתם זהה. יש  אפשרויות לבחור את הזוג. לאחר מכן נתייחס אל שני האיברים כאיבר אחד ונבחר פרמוטציה על n-1 איברים. הפתרון: .
ה.	n-2 איברים
פתרון: על מנת שהפונקציה תהיה על, או שיש שני זוגות איברים ב – A שתמונתם זהה – לכך יש  אפשרויות, או שיש שלושה איברים ב – A שתמונתם זהה – לכך יש  אפשרויות.
ו.	m איברים
פתרון: תהי . נסמן ב-  את קבוצת הפונקציות ש-  לא מופיע בתמונתן. מה שאנחנו מחפשים זה את .

בחיתוך של k קבוצות שונות יש  איברים. מנוסחת ההכלה וההפרדה נובע:

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

5.	מצא ביטוי סגור עבור הסדרות הבאות המוגדרות ברקורסיה:
א.	. תנאי התחלה: .
פתרון: הפולינום האופייני הוא  ששורשיו הם . לכן הפתרון הוא מהצורה . נציב n=0 ונקבל . נציב n=1 ונקבל . מכאן מתקבל . לכן הפתרון הוא .

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

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