Hausaufgabenblatt 4
Aufgabe HA 17 (Binomialkoeffizienten und Fakultäten II)
Unter Verwendung der Identität \[ \binom{n}{k}=\frac{n!}{k!(n-k)!} \] sind zu beweisen:
| (i) | \( \displaystyle\binom{n+1}{k+1}=\frac{n+1}{k+1}\cdot\binom{n}{k} \) für alle \( k,n\in\mathbb N_0 \) mit \( n\ge k \) |
| (ii) | \( \displaystyle\binom{n}{k}+\binom{n}{k+1}=\binom{n+1}{k+1} \) für alle \( k,n\in\mathbb N_0 \) mit \( n\ge k+1 \) |
Aufgabe HA 18 (Eine schwierige Identität)
Beweisen Sie \[ \sum_{k=0}^nk\binom{n}{k}=n\cdot 2^{n-1}\quad\mbox{für alle}\ n\in\mathbb N. \]
Aufgabe HA 19 (Zerlegungen endlicher Mengen)
Für \( n=1,2,3,4 \) betrachten wir Mengen \( A_n:=\{1,\ldots,n\} \) mit \( n \) Elementen.
| (i) | Bestimmen Sie jeweils sätliche Zerlegungen der Mengen \( A_n \) und damit die Bellschen Zahlen \( B_1,\ldots,B_4. \). |
| (ii) | Verifizieren Sie damit die Rekursionsformel |
\[ B_{n+1}=\sum_{k=0}^n\binom{n}{k}B_k\,,\quad n=0,1,2,3,4, \]
Aufgabe HA 20 (Anwendung von Präsenzaufgabe 16 I)
Es bezeichne \( M \) die Menge aller Zahlen \( 0\le m\le 20, \) die ohne Rest durch \( 3 \) oder durch \( 7 \) teilbar sind, d.h. \[ M=A\cup B \] mit den Mengen \[ \begin{array}{l} A:=\{m\in\mathbb N_0\,:\,3\ \mbox{teilt}\ m\ \mbox{ohne Rest}\}\,, \\[0.4ex] B:=\{m\in\mathbb N_0\,:\,7\ \mbox{teilt}\ m\ \mbox{ohne Rest}\}\,. \end{array} \] Bestimmen Sie \( |M|, \) und verifizieren Sie dabei die Mengenidentität aus PA 16.