Mercurial > 13ws.ds

comparison notes/tex/combinatorics.tex @ 44:5734c1faf9cd

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
tenth sheet and notes
author Markus Kaiser <markus.kaiser@in.tum.de>
date Mon, 06 Jan 2014 18:09:07 +0100
parents 7245dcccf68d
children e65f4b1a6e32
comparison
equal deleted inserted replaced
43:7245dcccf68d 44:5734c1faf9cd
23 &= n \cdot (n + 1) \cdot \ldots \cdot (n + m - 1) 23 &= n \cdot (n + 1) \cdot \ldots \cdot (n + m - 1)
24 \end{align} 24 \end{align}
25 } 25 }
26 \end{definition} 26 \end{definition}
27 \end{frame} 27 \end{frame}
28 28 }
29
30 \defineUnit{binomialkoeffizient}{%
29 \begin{frame} 31 \begin{frame}
30 \frametitle{Binomialkoeffizient} 32 \frametitle{Binomialkoeffizient}
31 \setbeamercovered{dynamic} 33 \setbeamercovered{dynamic}
32 34
33 \begin{definition}[Binomialkoeffizient] 35 \begin{definition}[Binomialkoeffizient]
37 \end{align} 39 \end{align}
38 Man sagt \structure{n über k} oder \structure{k aus n}. 40 Man sagt \structure{n über k} oder \structure{k aus n}.
39 \end{definition} 41 \end{definition}
40 \begin{itemize} 42 \begin{itemize}
41 \item $\binom{n}{k}$ viele Möglichkeiten, $k$ Elemente aus $n$ Elementen zu wählen 43 \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 \end{itemize}
44 45
45 \vfill 46 \vfill
46 47
47 \begin{example}[] 48 \begin{theorem}[Pascalsche Identität]
48 Forrest hat eine Schachtel mit 10 verschiedenen Pralinen.\\ 49 Die \structure{Pascalsche Identität} liefert eine rekursive Definition des Binomialkoeffizienten.
49 Wieviele Möglichkeiten gibt es, 4 davon zu essen? 50 \begin{align}
50 \begin{align} 51 \binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}
51 \binom{10}{4} = 210 52 \end{align}
52 \end{align} 53 \end{theorem}
53 \end{example} 54 \end{frame}
54 \end{frame} 55 }
55 56
57 \defineUnit{multimengen}{%
56 \begin{frame} 58 \begin{frame}
57 \frametitle{Multimengen} 59 \frametitle{Multimengen}
58 \setbeamercovered{dynamic} 60 \setbeamercovered{dynamic}
59 61
60 \begin{definition}[Multimenge] 62 \begin{definition}[Multimenge]
76 \begin{itemize} 78 \begin{itemize}
77 \item $M \defeq \left\{ 1, 2, 2, 2, 3 \right\} = \left\{ 2, 1, 2, 3, 2 \right\} \qquad \abs{M} = 5$ 79 \item $M \defeq \left\{ 1, 2, 2, 2, 3 \right\} = \left\{ 2, 1, 2, 3, 2 \right\} \qquad \abs{M} = 5$
78 \end{itemize} 80 \end{itemize}
79 \end{example} 81 \end{example}
80 \end{frame} 82 \end{frame}
83 }
81 } 84 }
82 85
83 \defineUnit{doppeltesabzaehlen}{% 86 \defineUnit{doppeltesabzaehlen}{%
84 \begin{frame} 87 \begin{frame}
85 \frametitle{Doppeltes Abzählen} 88 \frametitle{Doppeltes Abzählen}
133 \end{align} 136 \end{align}
134 Wenn man \structure{n} Elemente auf \structure{m < n} 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. 137 Wenn man \structure{n} Elemente auf \structure{m < n} 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.
135 \end{definition} 138 \end{definition}
136 \end{frame} 139 \end{frame}
137 } 140 }
141
142 \defineUnit{inklusionexklusion}{%
143 \begin{frame}
144 \frametitle{Inklusion und Exklusion}
145 \setbeamercovered{dynamic}
146
147 \begin{block}{Inklusion und Exklusion}
148 Das Prinzip der \structure{Inklusion und Exklusion} erweitert die Summenregel um \alert{nicht disjunkte} Mengen.\\
149 Für drei Mengen $A, B, C$ gilt
150 \begin{align}
151 \abs{A \cup B \cup C} = \abs{A} &\structure{+} \abs{B} \structure{+} \abs{C}\\
152 &\alert{-} \abs{A \cap B} \alert{-} \abs{A \cap C} \alert{-} \abs{B \cap C}\\
153 &\structure{+} \abs{A \cap B \cap C}
154 \end{align}
155 \end{block}
156 \vfill
157 \begin{center}
158 \begin{tikzpicture}[x=2em, y=2em]
159 \tikzstyle{opa} = [fill opacity=0.5]
160 \tikzstyle{A} = [tumred, fill=tumred!35, opa]
161 \tikzstyle{B} = [tumblue, fill=tumblue!35, opa]
162 \tikzstyle{C} = [tumgreen, fill=tumgreen!35, opa]
163 \draw[A] (-2, 0) ellipse (3 and 2);
164 \draw[B] (2, 0) ellipse (3 and 2);
165 \draw[C] (0, 2) ellipse (3 and 2);
166
167 \draw
168 (-3.5, -.5) node[tumred] {A}
169 (3.5, -.5) node[tumblue] {B}
170 (0, 3.5) node[tumgreen] {C}
171 (-2, -.5) node {1}
172 (2, -.5) node {1}
173 (0, 2.5) node {1}
174 (-1.5, 1) node {2}
175 (1.5, 1) node {2}
176 (0, -.5) node {2}
177 (0, .75) node {3};
178 \end{tikzpicture}
179 \end{center}
180 \end{frame}
181 }
182
183 \defineUnit{stirlingzahlen}{%
184 \begin{frame}
185 \frametitle{Mengenpartition}
186 \setbeamercovered{dynamic}
187
188 \begin{definition}[$k$-Partition]
189 Eine \structure{$k$-Partition} einer Menge $A$ ist eine Zerlegung von $A$ in $k$ \alert{disjunke, nichtleere Teilmengen} $A_1, \dots, A_k$ mit
190 \begin{align}
191 \biguplus_{i=1}^k A_i = A
192 \end{align}
193 Dabei bezeichnet $\uplus$ die disjunkte Vereinigung.
194 \end{definition}
195
196 \vfill
197
198 \begin{example}[]
199 Einige mögliche \structure{$3$-Partitionen} von $[5]$ sind
200 \begin{align}
201 \left\{ \left\{ 1,2 \right\}, \left\{ 3,4 \right\}, \left\{ 5 \right\} \right\} &&&
202 \left\{ \left\{ 1 \right\}, \left\{ 3,4 \right\}, \left\{ 2, 5 \right\} \right\}\\
203 \left\{ \left\{ 1,2,3 \right\}, \left\{ 4 \right\}, \left\{ 5 \right\} \right\} &&&
204 \left\{ \left\{ 1, 5 \right\}, \left\{ 2, 4 \right\}, \left\{ 3 \right\} \right\}
205 \end{align}
206 Es existieren genau 25 solche $3$-Partitionen.
207 \end{example}
208 \end{frame}
209
210 \begin{frame}
211 \frametitle{Stirlingzahlen zweiter Art}
212 \setbeamercovered{dynamic}
213
214 \begin{definition}[Stirlingzahlen zweiter Art]
215 Die \structure{Stirlingzahlen zweiter Art $S_{n, k}$} gibt die Anzahl der $k$-Partitoinen einer $n$-elementigen Menge an.
216 Wir schreiben
217 \begin{align}
218 \stirlingtwo{n}{k} &\defeq S_{n, k}\\
219 \intertext{Es ist}
220 \stirlingtwo{n}{k} &= \stirlingtwo{n-1}{k-1} + k \cdot \stirlingtwo{n-1}{k}
221 \end{align}
222 \end{definition}
223 \begin{itemize}
224 \item $\stirlingtwo{n}{k}$ viele Möglichkeiten, $n$ unterscheidbare Objekte in $k$ gleiche Fächer zu verteilen, sodass jedes Fach ein Objekt bekommt
225 \end{itemize}
226
227 \vfill
228
229 \begin{example}[]
230 \begin{itemize}
231 \item Es gibt $\stirlingtwo{5}{3} = 25$ $3$-Partitionen von $[5]$.
232 \end{itemize}
233 \end{example}
234 \end{frame}
235
236 \begin{frame}
237 \frametitle{Permutationen}
238 \setbeamercovered{dynamic}
239
240 \begin{definition}[Permutation]
241 Eine \structure{Permutation} einer Menge $A = \left\{ a_1, \dots, a_n \right\}$ ist eine \alert{bijektive Abbildung} $\pi : A \to A$.\\
242 Wir notieren Permutationen in zweizeiligen Vektoren.
243 \begin{align}
244 \pi = \begin{pmatrix}
245 a_1 & \dots & a_n \\
246 \pi(a_1) & \dots & \pi(a_n)
247 \end{pmatrix}
248 \end{align}
249 \end{definition}
250 \begin{itemize}
251 \item Weist jedem Element in $A$ ein neues, eindeutiges Element in $A$ zu.
252 \item \enquote{Mischt} die Elemente einer Menge
253 \end{itemize}
254
255 \vfill
256
257 \begin{example}[]
258 $\pi$ ist eine Permutation auf $[9]$.
259 \begin{align}
260 \pi = \begin{pmatrix}
261 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\
262 3 & 5 & 4 & 7 & 2 & 6 & 1 & 9 & 8
263 \end{pmatrix}
264 \end{align}
265 Es ist $\pi(1) = 3$, $\pi(4) = 7$.
266 \end{example}
267 \end{frame}
268
269 \begin{frame}
270 \frametitle{Zyklus}
271 \setbeamercovered{dynamic}
272
273 \begin{definition}[$k$-Zyklus]
274 Ein \structure{$k$-Zyklus} ist eine Permutation $\pi$, die $k$ verschiedene Zahlen $i_1, \dots, i_k$ im Kreis vertauscht.
275 \begin{align}
276 \pi &= \begin{pmatrix}
277 i_1 & i_2 & \dots & i_k \\
278 i_2 & i_3 & \dots & i_1
279 \end{pmatrix} \\
280 \intertext{Wir schreiben auch}
281 \pi &= \begin{pmatrix}
282 i_1 & i_2 & \dots & i_k
283 \end{pmatrix}
284 \end{align}
285 Jede Permutation ist eine Verkettung disjunkter Zyklen.
286 \end{definition}
287
288 \vfill
289
290 \begin{example}[]
291 % This is ugly :/
292 \vspace{-1em}
293 \begin{align}
294 \pi &= \begin{pmatrix}
295 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\
296 3 & 5 & 4 & 7 & 2 & 6 & 1 & 9 & 8
297 \end{pmatrix} \\
298 \intertext{$\pi$ enthält vier Zyklen.}
299 \pi &= \begin{pmatrix}
300 1 & 3 & 4 & 7
301 \end{pmatrix} \begin{pmatrix}
302 2 & 5
303 \end{pmatrix} \begin{pmatrix}
304 6
305 \end{pmatrix} \begin{pmatrix}
306 8 & 9
307 \end{pmatrix}
308 \end{align}
309 \end{example}
310 \end{frame}
311
312 \begin{frame}
313 \frametitle{Stirlingzahlen erster Art}
314 \setbeamercovered{dynamic}
315
316 \begin{definition}[Stirlingzahlen erster Art]
317 Die \structure{Stirlingzahlen erster Art $s_{n, k}$} gibt die Anzahl der Permutationen mit $n$ Elementen und \alert{k Zyklen} an.
318 Wir schreiben
319 \begin{align}
320 \stirlingone{n}{k} &\defeq s_{n, k}\\
321 \intertext{Es ist}
322 \stirlingone{n}{k} &= \stirlingone{n-1}{k-1} + (n-1) \cdot \stirlingone{n-1}{k}
323 \end{align}
324 \end{definition}
325
326 \begin{itemize}
327 \item Es gilt $\sum_{k=1}^n \stirlingone{n}{k} = n!$
328 \end{itemize}
329
330 \vfill
331
332 \begin{example}[]
333 \begin{itemize}
334 \item Es gibt $\stirlingone{9}{4} = 67284$ Permutationen über $[9]$ mit \alert{vier Zyklen}.
335 \end{itemize}
336 \end{example}
337 \end{frame}
338 }