Mercurial > 13ws.ds

comparison notes/tex/combinatorics.tex @ 39:0b7b90f84986

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
nineth sheet and notes
author Markus Kaiser <markus.kaiser@in.tum.de>
date Mon, 16 Dec 2013 22:35:38 +0100
parents
children 889a484514af
comparison
equal deleted inserted replaced
38:6aea8fe66bd6 39:0b7b90f84986
1 \defineUnit{zaehlen}{%
2 \begin{frame}
3 \frametitle{Faktorielle}
4 \setbeamercovered{dynamic}
5
6 \begin{definition}[Fakultät]
7 Die \structure{Fakultät $n!$} einer natürlichen Zahl $n \in \N_0$ ist
8 \[ n! \defeq \prod_{i=1}^n i = n \cdot (n - 1) \cdot \ldots \cdot 1 \]
9 mit $0! \defeq 1$.
10 \end{definition}
11
12 \vfill
13
14 \begin{definition}[Steigende und fallende Faktorielle]
15 Für $n, m \in \N_0$ mit $m \leq n$ ist
16 {
17 \setlength{\belowdisplayskip}{0pt}
18 \begin{align}
19 n^{\underline m} &\defeq \frac{n!}{(n-m)!} \tag{\structure{fallende Faktorielle}}\\
20 &= n \cdot (n - 1) \cdot \ldots \cdot (n - m + 1) \\
21 \intertext{\vspace{1em}}
22 n^{\overline m} &\defeq \frac{(n+m-1)!}{(n-1)!} \tag{\structure{steigende Faktorielle}}\\
23 &= n \cdot (n + 1) \cdot \ldots \cdot (n + m - 1)
24 \end{align}
25 }
26 \end{definition}
27 \end{frame}
28
29 \begin{frame}
30 \frametitle{Binomialkoeffizient}
31 \setbeamercovered{dynamic}
32
33 \begin{definition}[Binomialkoeffizient]
34 Der \structure{Binomialkoeffizient $\binom{n}{k}$} gibt die Anzahl der $k$-elementigen Teilmengen einer $n$-elementigen Menge an.
35 \begin{align}
36 \binom{n}{k} = \frac{n!}{k!(n-k)!} = \frac{n^{\underline k}}{k!}
37 \end{align}
38 Man sagt \structure{n über k} oder \structure{k aus n}.
39 \end{definition}
40 \begin{itemize}
41 \item $\binom{n}{k}$ viele Möglichkeiten, $k$ Elemente aus $n$ Elementen zu wählen
42 \item Rekursive Definition (hier nicht gezeigt)
43 \end{itemize}
44
45 \vfill
46
47 \begin{example}[]
48 Forrest hat eine Schachtel mit 10 verschiedenen Pralinen.\\ Wieviele Möglichkeiten gibt es, 4 davon zu essen?
49 \begin{itemize}
50 \item $\binom{10}{4} = 210$
51 \end{itemize}
52 \end{example}
53 \end{frame}
54
55 \begin{frame}
56 \frametitle{Multimengen}
57 \setbeamercovered{dynamic}
58
59 \begin{definition}[Multimenge]
60 \structure{Multimengen} sind eine Verallgemeinerung gewöhnlicher Mengen.\\
61 Elemente können nun mehrfach vorkommen, die Reihenfolge spielt weiterhin keine Rolle.\\
62 Sie werden meist auch mit $\left\{ \cdot \right\}$ notiert, alternativ $\{\!\vert \cdot \vert\!\}$.
63 \end{definition}
64
65 \begin{theorem}[Anzahl von Multiteilmengen]
66 Eine \structure{$k$-Multiteilmenge} von $M$ mit $\abs{M} = n$ ist eine Multimenge, die $k$ (nicht unbedingt verschiedene) Elemente aus $M$ enthält.\\
67 Es gibt
68 \begin{align}
69 \structure{\binom{k + n - 1}{k}} = \binom{k + n - 1}{n - 1}
70 \end{align}
71 solche Multiteilmengen.
72 \end{theorem}
73
74 \begin{example}[]
75 \begin{itemize}
76 \item $M \defeq \left\{ 1, 2, 2, 2, 3 \right\} = \left\{ 2, 1, 2, 3, 2 \right\} \qquad \abs{M} = 5$
77 \end{itemize}
78 \end{example}
79 \end{frame}
80 }
81
82 \defineUnit{doppeltesabzaehlen}{%
83 \begin{frame}
84 \frametitle{Doppeltes Abzählen}
85 \setbeamercovered{dynamic}
86
87 \begin{block}{Doppeltes Abzählen}
88 Ermittelt man die \structure{Mächtigkeit} einer Menge auf zwei Arten, so müssen beide Ergebnisse \structure{übereinstimmen}.\\
89 Eine so ermittelte Gleichung kann die gesuchte Mächtigkeit festlegen.
90 \end{block}
91
92 \begin{example}[Matrizen]
93 In einer Matrix müssen Zeilensummen und Spaltensummen übereinstimmen.
94 \end{example}
95
96 \begin{example}[Studenten]
97 In einer Vorlesung sitzen \structure{64 Studenten} und \alert{n Studentinnen}.\\
98 Jeder Student kennt genau \structure{5} Studentinnen und jede Studentin \alert{8}~Studenten.
99 Wenn \enquote{bekannt sein} symmetrisch ist, wie viele Studentinnen besuchen die Vorlesung?
100 {
101 \setlength{\belowdisplayskip}{0pt}
102 \begin{align}
103 \structure{64 \cdot 5} &= \alert{n \cdot 8}\\
104 n &= \frac{64 \cdot 5}{8} = 40
105 \end{align}
106 }
107 \end{example}
108 \end{frame}
109 }
110
111 \defineUnit{schubfachprinzip}{%
112 \begin{frame}
113 \frametitle{Schubfachprinzip}
114 \setbeamercovered{dynamic}
115
116 \begin{definition}[Schubfachprinzip]
117 Sei $f : X \to Y$ eine Abbildung und $\abs{X} > \abs{Y}$.\\
118 Dann gilt
119 \begin{align}
120 \exists y \in Y.\, \abs{f^{-1}(y)} \geq \alert{2}
121 \end{align}
122 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.
123 \end{definition}
124
125 \vfill
126
127 \begin{definition}[Verallgemeinertes Schubfachprinzip]
128 Sei $f : X \to Y$ eine Abbildung und $\abs{X} > \abs{Y}$.\\
129 Dann gilt
130 \begin{align}
131 \exists y \in Y.\, \abs{f^{-1}(y)} \geq \alert{\left \lceil \frac{\abs{X}}{\abs{Y}}\right \rceil}
132 \end{align}
133 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.
134 \end{definition}
135 \end{frame}
136 }