# HG changeset patch # User Markus Kaiser # Date 1389028147 -3600 # Node ID 5734c1faf9cde56b704912c1b04c18d267bf5d9b # Parent 7245dcccf68d658f717b329659a8ec20a661f0b7 tenth sheet and notes diff -r 7245dcccf68d -r 5734c1faf9cd ds13-10.pdf Binary file ds13-10.pdf has changed diff -r 7245dcccf68d -r 5734c1faf9cd notes/tex/combinatorics.tex --- 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} +} diff -r 7245dcccf68d -r 5734c1faf9cd notes/tex/complete_notes.tex --- 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} diff -r 7245dcccf68d -r 5734c1faf9cd notes/tex/preamble.tex --- 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 diff -r 7245dcccf68d -r 5734c1faf9cd notes/tex/ue09_notes.tex --- 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} diff -r 7245dcccf68d -r 5734c1faf9cd notes/tex/ue10_notes.tex --- /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} diff -r 7245dcccf68d -r 5734c1faf9cd notes/ue10_notes.pdf Binary file notes/ue10_notes.pdf has changed