# HG changeset patch # User Markus Kaiser # Date 1387229738 -3600 # Node ID 0b7b90f8498664e8155d72cc136559ea47c618e2 # Parent 6aea8fe66bd699b05eb0149c29b1b6dbd6c3f2a8 nineth sheet and notes diff -r 6aea8fe66bd6 -r 0b7b90f84986 ds13-09.pdf Binary file ds13-09.pdf has changed diff -r 6aea8fe66bd6 -r 0b7b90f84986 notes/tex/combinatorics.tex --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/notes/tex/combinatorics.tex Mon Dec 16 22:35:38 2013 +0100 @@ -0,0 +1,136 @@ +\defineUnit{zaehlen}{% +\begin{frame} + \frametitle{Faktorielle} + \setbeamercovered{dynamic} + + \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} + +\begin{frame} + \frametitle{Binomialkoeffizient} + \setbeamercovered{dynamic} + + \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 + \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{itemize} + \item $\binom{10}{4} = 210$ + \end{itemize} + \end{example} +\end{frame} + +\begin{frame} + \frametitle{Multimengen} + \setbeamercovered{dynamic} + + \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} + \setbeamercovered{dynamic} + + \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 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} + \setbeamercovered{dynamic} + + \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 < m} 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 < m} 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} +} diff -r 6aea8fe66bd6 -r 0b7b90f84986 notes/tex/complete_notes.tex --- a/notes/tex/complete_notes.tex Tue Dec 10 11:59:09 2013 +0100 +++ b/notes/tex/complete_notes.tex Mon Dec 16 22:35:38 2013 +0100 @@ -46,4 +46,13 @@ %ue07 \showUnit{natuerlichesschliessenquantoren} \showUnit{induktion} + +%ue08 +\showUnit{wohlfundierteinduktion} +\showUnit{landausymbole} + +%ue09 +\showUnit{zaehlen} +\showUnit{doppeltesabzaehlen} +\showUnit{schubfachprinzip} \end{document} diff -r 6aea8fe66bd6 -r 0b7b90f84986 notes/tex/frames.tex --- a/notes/tex/frames.tex Tue Dec 10 11:59:09 2013 +0100 +++ b/notes/tex/frames.tex Mon Dec 16 22:35:38 2013 +0100 @@ -11,3 +11,4 @@ \input{basics.tex} \input{logic.tex} \input{growth.tex} +\input{combinatorics.tex} diff -r 6aea8fe66bd6 -r 0b7b90f84986 notes/tex/ue09_notes.tex --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/notes/tex/ue09_notes.tex Mon Dec 16 22:35:38 2013 +0100 @@ -0,0 +1,13 @@ +\input{preamble.tex} +\input{frames.tex} + +\title{Übung 9: Zählen \& Schubfachprinzip} +\subtitle{Diskrete Strukturen im Wintersemester 2013/2014} +\author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}} + +\begin{document} +\showUnit{titel} +\showUnit{zaehlen} +\showUnit{doppeltesabzaehlen} +\showUnit{schubfachprinzip} +\end{document} diff -r 6aea8fe66bd6 -r 0b7b90f84986 notes/ue09_notes.pdf Binary file notes/ue09_notes.pdf has changed