\defineUnit{zaehlen}{%
\begin{frame}
    \frametitle{Faktorielle}

    \begin{definition}[Fakultät]
        Die \structure{Fakultät $n!$} einer natürlichen Zahl $n \in \N_0$ ist
        \[ n! \defeq \prod_{i=1}^n i = n \cdot (n - 1) \cdot \ldots \cdot 1 \]
        mit $0! \defeq 1$.
    \end{definition}

    \vfill

    \begin{definition}[Steigende und fallende Faktorielle]
        Für $n, m \in \N_0$ mit $m \leq n$ ist
        {
            \setlength{\belowdisplayskip}{0pt}
            \begin{align}
                n^{\underline m} &\defeq \frac{n!}{(n-m)!} \tag{\structure{fallende Faktorielle}}\\
                &= n \cdot (n - 1) \cdot \ldots \cdot (n - m + 1) \\
                \intertext{\vspace{1em}}
                n^{\overline m} &\defeq \frac{(n+m-1)!}{(n-1)!} \tag{\structure{steigende Faktorielle}}\\
                &= n \cdot (n + 1) \cdot \ldots \cdot (n + m - 1)
            \end{align}
        }
    \end{definition}
\end{frame}
}

\defineUnit{binomialkoeffizient}{%
\begin{frame}
    \frametitle{Binomialkoeffizient}

    \begin{definition}[Binomialkoeffizient]
        Der \structure{Binomialkoeffizient $\binom{n}{k}$} gibt die Anzahl der $k$-elementigen Teilmengen einer $n$-elementigen Menge an.
        \begin{align}
            \binom{n}{k} = \frac{n!}{k!(n-k)!} = \frac{n^{\underline k}}{k!}
        \end{align}
        Man sagt \structure{n über k} oder \structure{k aus n}.
    \end{definition}
    \begin{itemize}
        \item $\binom{n}{k}$ viele Möglichkeiten, $k$ Elemente aus $n$ Elementen zu wählen
    \end{itemize}

    \vfill

    \begin{theorem}[Pascalsche Identität]
        Die \structure{Pascalsche Identität} liefert eine rekursive Definition des Binomialkoeffizienten.
        \begin{align}
            \binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}
        \end{align}
    \end{theorem}
\end{frame}
}

\defineUnit{multimengen}{%
\begin{frame}
    \frametitle{Multimengen}

    \begin{definition}[Multimenge]
        \structure{Multimengen} sind eine Verallgemeinerung gewöhnlicher Mengen.\\
        Elemente können nun mehrfach vorkommen, die Reihenfolge spielt weiterhin keine Rolle.\\
        Sie werden meist auch mit $\left\{ \cdot \right\}$ notiert, alternativ $\{\!\vert \cdot \vert\!\}$.
    \end{definition}

    \begin{theorem}[Anzahl von Multiteilmengen]
        Eine \structure{$k$-Multiteilmenge} von $M$ mit $\abs{M} = n$ ist eine Multimenge, die $k$ (nicht unbedingt verschiedene) Elemente aus $M$ enthält.\\
        Es gibt
        \begin{align}
            \structure{\binom{k + n - 1}{k}} = \binom{k + n - 1}{n - 1}
        \end{align}
        solche Multiteilmengen.
    \end{theorem}

    \begin{example}[]
        \begin{itemize}
            \item $M \defeq \left\{ 1, 2, 2, 2, 3 \right\} = \left\{ 2, 1, 2, 3, 2 \right\} \qquad \abs{M} = 5$
        \end{itemize}
    \end{example}
\end{frame}
}
}

\defineUnit{doppeltesabzaehlen}{%
\begin{frame}
    \frametitle{Doppeltes Abzählen}

    \begin{block}{Doppeltes Abzählen}
        Ermittelt man die \structure{Mächtigkeit} einer Menge auf zwei Arten, so müssen beide Ergebnisse \structure{übereinstimmen}.\\
        Eine so ermittelte Gleichung kann die gesuchte Mächtigkeit festlegen.
    \end{block}

    \begin{example}[Matrizen]
        In einer Matrix müssen die Summen von Zeilensummen und Spaltensummen übereinstimmen.
    \end{example}

    \begin{example}[Studenten]
        In einer Vorlesung sitzen \structure{64 Studenten} und \alert{n Studentinnen}.\\
        Jeder Student kennt genau \structure{5} Studentinnen und jede Studentin \alert{8}~Studenten.
        Wenn \enquote{bekannt sein} symmetrisch ist, wie viele Studentinnen besuchen die Vorlesung?
        {
            \setlength{\belowdisplayskip}{0pt}
            \begin{align}
                \structure{64 \cdot 5} &= \alert{n \cdot 8}\\
                n &= \frac{64 \cdot 5}{8} = 40
            \end{align}
        }
    \end{example}
\end{frame}
}

\defineUnit{schubfachprinzip}{%
\begin{frame}
    \frametitle{Schubfachprinzip}

    \begin{definition}[Schubfachprinzip]
        Sei $f : X \to Y$ eine Abbildung und $\abs{X} > \abs{Y}$.\\
        Dann gilt
        \begin{align}
            \exists y \in Y.\, \abs{f^{-1}(y)} \geq \alert{2}
        \end{align}
        Wenn man \structure{n} Elemente auf \structure{m < n} Fächer verteilt, dann gibt es \structure{mindestens ein Fach}, das mindestens \structure{2} Elemente enthält.
    \end{definition}

    \vfill

    \begin{definition}[Verallgemeinertes Schubfachprinzip]
        Sei $f : X \to Y$ eine Abbildung und $\abs{X} > \abs{Y}$.\\
        Dann gilt
        \begin{align}
            \exists y \in Y.\, \abs{f^{-1}(y)} \geq \alert{\left \lceil \frac{\abs{X}}{\abs{Y}}\right \rceil}
        \end{align}
        Wenn man \structure{n} Elemente auf \structure{m < n} Fächer verteilt, dann gibt es \structure{mindestens ein Fach}, das mindestens \structure{$\left\lceil\frac{\abs{X}}{\abs{Y}} \right\rceil$} Elemente enthält.
    \end{definition}
\end{frame}
}

\defineUnit{inklusionexklusion}{%
\begin{frame}
    \frametitle{Inklusion und Exklusion}

    \begin{block}{Inklusion und Exklusion}
        Das Prinzip der \structure{Inklusion und Exklusion} erweitert die Summenregel um \alert{nicht disjunkte} Mengen.\\
        Für drei Mengen $A, B, C$ gilt
        \begin{align}
            \abs{A \cup B \cup C} = \abs{A} &\structure{+} \abs{B} \structure{+} \abs{C}\\
            &\alert{-} \abs{A \cap B} \alert{-} \abs{A \cap C} \alert{-} \abs{B \cap C}\\
            &\structure{+} \abs{A \cap B \cap C}
        \end{align}
    \end{block}
    \vfill
    \begin{center}
        \begin{tikzpicture}[x=2em, y=2em]
            \tikzstyle{opa} = [fill opacity=0.5]
            \tikzstyle{A} = [tumred, fill=tumred!35, opa]
            \tikzstyle{B} = [tumblue, fill=tumblue!35, opa]
            \tikzstyle{C} = [tumgreen, fill=tumgreen!35, opa]
            \draw[A] (-2, 0) ellipse (3 and 2);
            \draw[B] (2, 0) ellipse (3 and 2);
            \draw[C] (0, 2) ellipse (3 and 2);

            \draw
                (-3.5, -.5) node[tumred] {A}
                (3.5, -.5) node[tumblue] {B}
                (0, 3.5) node[tumgreen] {C}
                (-2, -.5) node {1}
                (2, -.5) node {1}
                (0, 2.5) node {1}
                (-1.5, 1) node {2}
                (1.5, 1) node {2}
                (0, -.5) node {2}
                (0, .75) node {3};
        \end{tikzpicture}
    \end{center}
\end{frame}
}

\defineUnit{stirlingzahlen}{%
\begin{frame}
    \frametitle{Mengenpartition}

    \begin{definition}[$k$-Partition]
        Eine \structure{$k$-Partition} einer Menge $A$ ist eine Zerlegung von $A$ in $k$ \alert{disjunke, nichtleere Teilmengen} $A_1, \dots, A_k$ mit
        \begin{align}
            \biguplus_{i=1}^k A_i = A
        \end{align}
        Dabei bezeichnet $\uplus$ die disjunkte Vereinigung.
    \end{definition}

    \vfill

    \begin{example}[]
        Einige mögliche \structure{$3$-Partitionen} von $[5]$ sind
        \begin{align}
            \left\{ \left\{ 1,2 \right\}, \left\{ 3,4 \right\}, \left\{ 5 \right\} \right\} &&&
            \left\{ \left\{ 1 \right\}, \left\{ 3,4 \right\}, \left\{ 2, 5 \right\} \right\}\\
            \left\{ \left\{ 1,2,3 \right\}, \left\{ 4 \right\}, \left\{ 5 \right\} \right\} &&&
            \left\{ \left\{ 1, 5 \right\}, \left\{ 2, 4 \right\}, \left\{ 3 \right\} \right\}
        \end{align}
        Es existieren genau 25 solche $3$-Partitionen.
    \end{example}
\end{frame}

\begin{frame}
    \frametitle{Stirlingzahlen zweiter Art}

    \begin{definition}[Stirlingzahlen zweiter Art]
        Die \structure{Stirlingzahlen zweiter Art $S_{n, k}$} gibt die Anzahl der $k$-Partitoinen einer $n$-elementigen Menge an.
        Wir schreiben
        \begin{align}
            \stirlingtwo{n}{k} &\defeq S_{n, k}\\
            \intertext{Es ist}
            \stirlingtwo{n}{k} &= \stirlingtwo{n-1}{k-1} + k \cdot \stirlingtwo{n-1}{k}
        \end{align}
    \end{definition}
    \begin{itemize}
        \item $\stirlingtwo{n}{k}$ viele Möglichkeiten, $n$ unterscheidbare Objekte in $k$ gleiche Fächer zu verteilen, sodass jedes Fach ein Objekt bekommt
    \end{itemize}

    \vfill

    \begin{example}[]
        \begin{itemize}
            \item Es gibt $\stirlingtwo{5}{3} = 25$ $3$-Partitionen von $[5]$.
        \end{itemize}
    \end{example}
\end{frame}

\begin{frame}
    \frametitle{Permutationen}

    \begin{definition}[Permutation]
        Eine \structure{Permutation} einer Menge $A = \left\{ a_1, \dots, a_n \right\}$ ist eine \alert{bijektive Abbildung} $\pi : A \to A$.\\
        Wir notieren Permutationen in zweizeiligen Vektoren.
        \begin{align}
            \pi = \begin{pmatrix}
                a_1 & \dots & a_n \\
                \pi(a_1) & \dots & \pi(a_n)
            \end{pmatrix}
        \end{align}
    \end{definition}
    \begin{itemize}
        \item Weist jedem Element in $A$ ein neues, eindeutiges Element in $A$ zu.
        \item \enquote{Mischt} die Elemente einer Menge
    \end{itemize}

    \vfill

    \begin{example}[]
        $\pi$ ist eine Permutation auf $[9]$.
        \begin{align}
            \pi = \begin{pmatrix}
                1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\
                3 & 5 & 4 & 7 & 2 & 6 & 1 & 9 & 8
            \end{pmatrix}
        \end{align}
        Es ist $\pi(1) = 3$, $\pi(4) = 7$.
    \end{example}
\end{frame}

\begin{frame}
    \frametitle{Zyklus}

    \begin{definition}[$k$-Zyklus]
        Ein \structure{$k$-Zyklus} ist eine Permutation $\pi$, die $k$ verschiedene Zahlen $i_1, \dots, i_k$ im Kreis vertauscht.
        \begin{align}
            \pi &= \begin{pmatrix}
                i_1 & i_2 & \dots & i_k \\
                i_2 & i_3 & \dots & i_1
            \end{pmatrix} \\
            \intertext{Wir schreiben auch}
            \pi &= \begin{pmatrix}
                i_1 & i_2 & \dots & i_k
            \end{pmatrix}
        \end{align}
        Jede Permutation ist eine Verkettung disjunkter Zyklen.
    \end{definition}

    \vfill

    \begin{example}[]
        % This is ugly :/
        \vspace{-1em}
        \begin{align}
            \pi &= \begin{pmatrix}
                1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\
                3 & 5 & 4 & 7 & 2 & 6 & 1 & 9 & 8
            \end{pmatrix} \\
            \intertext{$\pi$ enthält vier Zyklen.}
            \pi &= \begin{pmatrix}
                1 & 3 & 4 & 7
            \end{pmatrix} \begin{pmatrix}
                2 & 5
            \end{pmatrix} \begin{pmatrix}
                6
            \end{pmatrix} \begin{pmatrix}
                8 & 9
            \end{pmatrix}
        \end{align}
    \end{example}
\end{frame}

\begin{frame}
    \frametitle{Stirlingzahlen erster Art}

    \begin{definition}[Stirlingzahlen erster Art]
        Die \structure{Stirlingzahlen erster Art $s_{n, k}$} gibt die Anzahl der Permutationen mit $n$ Elementen und \alert{k Zyklen} an.
        Wir schreiben
        \begin{align}
            \stirlingone{n}{k} &\defeq s_{n, k}\\
            \intertext{Es ist}
            \stirlingone{n}{k} &= \stirlingone{n-1}{k-1} + (n-1) \cdot \stirlingone{n-1}{k}
        \end{align}
    \end{definition}

    \begin{itemize}
        \item Es gilt $\sum_{k=1}^n \stirlingone{n}{k} = n!$
    \end{itemize}

    \vfill

    \begin{example}[]
        \begin{itemize}
            \item Es gibt $\stirlingone{9}{4} = 67284$ Permutationen über $[9]$ mit \alert{vier Zyklen}.
        \end{itemize}
    \end{example}
\end{frame}
}