תרגיל 11 – מתמטיקה בדידה

1.	הביאו נימוקים קומבינטורים מדוע  מספר שלם ומדוע  גם כן מספר שלם.

2.	הוכח:
א.	
ב.	

3.	תהינה A ו B קבוצות. |A|=n כאשר n>3 טבעי. מה עוצמת הקבוצה  אם בקבוצה B יש:
א.	איבר אחד.
ב.	שני איברים.
ג.	n איברים.
ד.	n-1 איברים.
ה.	n-2 איברים.
ו.	m איברים (m>2 טבעי).

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

5.	מצא ביטוי סגור עבור הסדרות הבאות המוגדרות ברקורסיה:
א.	 (לכל n טבעי). תנאי התחלה: .
ב.	 (לכל n טבעי). תנאי התחלה: .

6.	חשב את:
א.	
ב.	
ג.	
ד.	
ה.	
ו.	
ז.	
7.	תהי . נסמן ב B את קבוצת כל הפונקציות  מ A ל A שהן חח"ע ועל A. חשב את עוצמת הקבוצות הבאות:
א.	
ב.	
ג.	
8.	נתונים n זוגות של אח ואחות. רוצים ליצור שידוך לכולם באופן תקין (אין לשדך אחות לאחיה).
א.	בכמה דרכים ניתן לעשות זאת?
ב.	נתון בנוסף כי k מזוגות האחים והאחיות הם גבוהים והשאר נמוכים. בכמה דרכים ניתן לשדכם כך שגבוהים ישודכו רק עם גבוהות ונמוכים רק עם נמוכות?

בהצלחה