\documentclass{uebungsblatt}
\author{Marek Kubica, kubica@in.tum.de}
\fach{Diskrete Strukturen}
\blatt{11}
\gruppe{11}

\begin{document}

\aufgabe

\teilaufgabe

Da es für jede Zahl $\in [n]$ nur drei Möglichkeiten gibt: entweder sie kommt
in $A_1$ vor oder sie kommt in $A_2$ vor (sie kann nicht sowohl in $A_1$ als
auch in $A_2$ vorkommen, da die Mengen laut Angabe disjunkt sein sollen) oder
sie kommt in keine von beiden vor. Da es also $n$ Zahlen gibt, führt das zu
$3^n$ Lösungen.

\teilaufgabe

Wenn man das maximale mögliche Tupel bildet ist dies $(5, 5, 5, 5, 5)$ und
dessen Summe ist 25, also $25 - 21 = 4$ zu viel. Somit muss man die 
Möglichkeiten bilden, von diesem Tupel 4 abzuziehen. Somit sind
die Möglichkeiten:

\begin{enumerate}
  \item $(5, 5, 5, 5, 1)$ als ungeordete Menge was $\frac{5!}{4!} = 5$
    Möglichkeiten für geordnete Tupel entspricht.
  \item $(5, 5, 5, 4, 2)$ als ungeordete Menge was $\frac{5!}{3!} = 20$
    Möglichkeiten für geordnete Tupel entspricht.
  \item $(5, 5, 5, 3, 3)$ als ungeordete Menge was $\frac{5!}{3! \cdot 2!} = 10$
    Möglichkeiten für geordnete Tupel entspricht
  \item $(5, 5, 4, 4, 3)$ als ungeordete Menge was $\frac{5!}{2! \cdot 2!} = 30$
    Möglichkeiten für geordnete Tupel entspricht
  \item $(5, 4, 4, 4, 4)$ als ungeordete Menge was $\frac{5!}{4!} = 5$
    Möglichkeiten für geordnete Tupel entspricht
\end{enumerate}

Die Summe ist $5 + 20 + 10 + 30 + 5 = 70$, was genau der Anzahl der
Lösungen für die Gleichung entspricht.

\aufgabe

Es sollen $n$ Elemente in $n-2$ Mengen verteilt werden. Dies entspricht den
Stirling-Zahlen zweiter Art $S_{n,k}$ aber da $n$ und $k$ nicht unabhängig
sind, lässt sich eine Beobachtung anstellen, dass die Anzahl der Mengen
auch nichtrekursiv zu bestimmen ist.

Es gibt für $n = n$ und $k = n - 2$ nur zwei mögliche Konfigurationen:

\begin{itemize}
  \item Es gibt eine Partition mit drei Elementen, die anderen Partitionen
    müssen einelementig sein. Die Reihenfolge ist beliebig, also ist für die
    dreielementige Menge die Anzahl der Möglichkeiten ${n \choose 3} $ 
    (3 Elemente aus $n$ ziehen ohne Zurücklegen, ohne Beachtung der
    Reihenfolge). Die restlichen $n-3$ Zahlen sind beliebig.
  \item Es gibt zwei Partitionen mit je zwei Elementen, die anderen
    Partitionen müssen einelementig sein. Analog zu der ersten Möglichkeit
    gibt es also für die erste zweielementige Menge ${n \choose 2}$
    Möglichkeiten, für die zweite nur noch ${n-2 \choose 2}$ Möglichkeiten.
    Die restlichen Elemente sind egal, da daren reihenfolge keine Rolle
    spielt. Da aber in dem Fall ${\{1, 2\}, \{3, 4\}, \{5\}, \{6}\}$ und
    ${\{3, 4\}, \{1, 2\}, \{5\}, \{6}\}$ als unterschiedliche Möglichkeiten
    gewertet werden würden, muss noch mit $\frac{1}{2}$ multipliziert werden
    damit die Reihenfolge der beiden zweielementigen Mengen keine Rolle 
    spielt.
\end{itemize}

Somit ist nun

\begin{flalign*}
S_{n,n-2} & = {n \choose 3} + {n \choose 2}{n - 2 \choose 2} \cdot \frac{1}{2} & \\
 & = \frac{n!}{3! \cdot (3-n)!} + \frac{n!}{2! \cdot (n-2)!} \cdot \frac{(n-1)!}{2! \cdot (n-2-2)!} \cdot \frac{1}{2} & \text{Binomialkoeffizient aufgelöst} \\
 & = \frac{n!}{3! \cdot (3-n)!} + \frac{n!}{2!} \cdot \frac{1}{2! \cdot (n-4)!} \cdot \frac{1}{2} & (n-2)! \text{ gekürzt} \\
 & = \frac{n!}{6 \cdot (3-n)!} + \frac{1}{8 \cdot (n-4)!} & \\
 & = \frac{n \cdot (n-1) \cdot (n-2)}{6} + \frac{n \cdot (n-1) \cdot (n-2) \cdot (n-3)}{8} & \text{Fakultäten gekürzt} \\
 & = \frac{4 \cdot n \cdot (n-1) \cdot (n-2)}{24} + \frac{3 \cdot n \cdot (n-1) \cdot (n-2) \cdot (n-3)}{24} & \\
 & = \frac{4 \cdot n \cdot (n-1) \cdot (n-2) + 3 \cdot n \cdot (n-1) \cdot (n-2) \cdot (n-3)}{24} & \\
 & = \frac{1}{24} \cdot 4 \cdot n \cdot (n-1) \cdot (n-2) + 3 \cdot n \cdot (n-1) \cdot (n-2) \cdot (n-3) & \\
 & = \frac{1}{24} \cdot n \cdot (n-1) \cdot (n-2) \left(4 + 3 \cdot (n-3)\right) & \\
 & = \frac{1}{24} \cdot n \cdot (n-1) \cdot (n-2) \left(4 + 3n - 9\right) & \\
 & = \frac{1}{24} \cdot n \cdot (n-1) \cdot (n-2) (3n - 5) & \qed \\
\end{flalign*}

\aufgabe

\teilaufgabe

Da $T_k$ eine k-elementige Klasse ist bedeutet dies, dass es nur noch $n-k$
Elemente gibt, die nicht in dieser Klasse sind und die noch in (beliebige)
Partitionen eingeteilt werden können, also $B_{n-k}$. Wenn nun ein Element in
der Menge hinzugefügt wird gäbe es $B_{n+1-k}$ freie Elemente über die
Partitionen gebildet werden können. Da aber das soeben hinzugefügte Element in
die Klasse $T_k$ aufgenommen wird, existieren wieder nur $n-k$ freie Elemente
$n+1$ elementigen Menge die in Partitionen eingeteilt werden könnnen, somit ist
die Menge der möglichen Partitionen weiterhin $B_{n-k}$. Man könnte auch
argumentieren dass aus der $n$-elementigen Menge die $n+1$-elementige Menge
wird und aus $T_k$ $T_{k+1}$ und die Formel dann $B_{(n+1)-(k+1)} = B_{n+1-k-1}
= B_{n-k}$ wird.

\teilaufgabe

Um die Anzahl der Partitionen einer $n+1$-elementigen Menge zu bilden, muss man
an zu jeder Partition der Länge 0 bis $n$ ein Element hinzufügen.  Um das
Element hinzuzufügen gibt es für jede Menge der Länge $k$ ${n \choose k}$
Möglichkeiten (da die Reihenfolge egal ist). Diese Möglichkeiten werden von
$k=0$ (also die Partitionen der $n$ elementigen Menge) bis $k=n$ (also die
Anzahl der Partitionen der leeren Menge) aufsummiert, was sicherstellt dass
alle Partitionen der Länge $B_{n-k}$ gezählt werden werden.

Somit gilt die Formel $B_{n+1} = \sum_{k=0}^{n} {n \choose k} B_{n-k}$

\end{document}