changeset 39:0b7b90f84986

nineth sheet and notes
author Markus Kaiser <markus.kaiser@in.tum.de>
date Mon, 16 Dec 2013 22:35:38 +0100
parents 6aea8fe66bd6
children 889a484514af
files ds13-09.pdf notes/tex/combinatorics.tex notes/tex/complete_notes.tex notes/tex/frames.tex notes/tex/ue09_notes.tex notes/ue09_notes.pdf
diffstat 6 files changed, 159 insertions(+), 0 deletions(-) [+]
line wrap: on
line diff
Binary file ds13-09.pdf has changed
--- /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}
+}
--- 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}
--- 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}
--- /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}
Binary file notes/ue09_notes.pdf has changed