Binary file ds13-10.pdf has changed

--- a/notes/tex/combinatorics.tex	Tue Dec 17 00:56:39 2013 +0100
+++ b/notes/tex/combinatorics.tex	Mon Jan 06 18:09:07 2014 +0100
@@ -25,7 +25,9 @@
         }
     \end{definition}
 \end{frame}
+}
 
+\defineUnit{binomialkoeffizient}{%
 \begin{frame}
     \frametitle{Binomialkoeffizient}
     \setbeamercovered{dynamic}
@@ -39,20 +41,20 @@
     \end{definition}
     \begin{itemize}
         \item $\binom{n}{k}$ viele Möglichkeiten, $k$ Elemente aus $n$ Elementen zu wählen
-        \item Rekursive Definition (hier nicht gezeigt)
     \end{itemize}
 
     \vfill
 
-    \begin{example}[]
-        Forrest hat eine Schachtel mit 10 verschiedenen Pralinen.\\
-        Wieviele Möglichkeiten gibt es, 4 davon zu essen?
+    \begin{theorem}[Pascalsche Identität]
+        Die \structure{Pascalsche Identität} liefert eine rekursive Definition des Binomialkoeffizienten.
         \begin{align}
-            \binom{10}{4} = 210
+            \binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}
         \end{align}
-    \end{example}
+    \end{theorem}
 \end{frame}
+}
 
+\defineUnit{multimengen}{%
 \begin{frame}
     \frametitle{Multimengen}
     \setbeamercovered{dynamic}
@@ -79,6 +81,7 @@
     \end{example}
 \end{frame}
 }
+}
 
 \defineUnit{doppeltesabzaehlen}{%
 \begin{frame}
@@ -135,3 +138,201 @@
     \end{definition}
 \end{frame}
 }
+
+\defineUnit{inklusionexklusion}{%
+\begin{frame}
+    \frametitle{Inklusion und Exklusion}
+    \setbeamercovered{dynamic}
+
+    \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}
+    \setbeamercovered{dynamic}
+
+    \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}
+    \setbeamercovered{dynamic}
+
+    \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}
+    \setbeamercovered{dynamic}
+
+    \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}
+    \setbeamercovered{dynamic}
+
+    \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}
+    \setbeamercovered{dynamic}
+
+    \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}
+}

--- a/notes/tex/complete_notes.tex	Tue Dec 17 00:56:39 2013 +0100
+++ b/notes/tex/complete_notes.tex	Mon Jan 06 18:09:07 2014 +0100
@@ -53,6 +53,12 @@
 
 %ue09
 \showUnit{zaehlen}
+\showUnit{binomialkoeffizient}
+\showUnit{multimengen}
 \showUnit{doppeltesabzaehlen}
 \showUnit{schubfachprinzip}
+
+%ue10
+\showUnit{inklusionexklusion}
+\showUnit{stirlingzahlen}
 \end{document}

--- a/notes/tex/preamble.tex	Tue Dec 17 00:56:39 2013 +0100
+++ b/notes/tex/preamble.tex	Mon Jan 06 18:09:07 2014 +0100
@@ -57,6 +57,8 @@
 \newcommand{\setsymdiff}{\,\triangle\,}
 
 \newcommand{\rel}[1]{\,\mathrm{#1}\,}
+\DeclareRobustCommand{\stirlingone}{\genfrac{[}{]}{0pt}{}}
+\DeclareRobustCommand{\stirlingtwo}{\genfrac\{\}{0pt}{}}
 
 \newcommand{\defeq}{\coloneqq} %Mathtools already defines this
 

--- a/notes/tex/ue09_notes.tex	Tue Dec 17 00:56:39 2013 +0100
+++ b/notes/tex/ue09_notes.tex	Mon Jan 06 18:09:07 2014 +0100
@@ -8,6 +8,8 @@
 \begin{document}
 \showUnit{titel}
 \showUnit{zaehlen}
+\showUnit{binomialkoeffizient}
+\showUnit{multimengen}
 \showUnit{doppeltesabzaehlen}
 \showUnit{schubfachprinzip}
 \end{document}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/notes/tex/ue10_notes.tex	Mon Jan 06 18:09:07 2014 +0100
@@ -0,0 +1,13 @@
+\input{preamble.tex}
+\input{frames.tex}
+
+\title{Übung 10: Inklusion/Exklusion \& Stirlingzahlen}
+\subtitle{Diskrete Strukturen im Wintersemester 2013/2014}
+\author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}}
+
+\begin{document}
+\showUnit{titel}
+\showUnit{inklusionexklusion}
+\showUnit{binomialkoeffizient}
+\showUnit{stirlingzahlen}
+\end{document}

Binary file notes/ue10_notes.pdf has changed