Mercurial > 13ws.ds

annotate 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
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
39
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
1 \defineUnit{zaehlen}{%
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
2 \begin{frame}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
3 \frametitle{Faktorielle}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
4 \setbeamercovered{dynamic}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
5
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
6 \begin{definition}[Fakultät]
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
7 Die \structure{Fakultät $n!$} einer natürlichen Zahl $n \in \N_0$ ist
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
8 \[ n! \defeq \prod_{i=1}^n i = n \cdot (n - 1) \cdot \ldots \cdot 1 \]
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
9 mit $0! \defeq 1$.
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
10 \end{definition}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
11
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
12 \vfill
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
13
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
14 \begin{definition}[Steigende und fallende Faktorielle]
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
15 Für $n, m \in \N_0$ mit $m \leq n$ ist
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
16 {
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
17 \setlength{\belowdisplayskip}{0pt}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
18 \begin{align}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
19 n^{\underline m} &\defeq \frac{n!}{(n-m)!} \tag{\structure{fallende Faktorielle}}\\
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
20 &= n \cdot (n - 1) \cdot \ldots \cdot (n - m + 1) \\
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
21 \intertext{\vspace{1em}}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
22 n^{\overline m} &\defeq \frac{(n+m-1)!}{(n-1)!} \tag{\structure{steigende Faktorielle}}\\
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
23 &= n \cdot (n + 1) \cdot \ldots \cdot (n + m - 1)
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
24 \end{align}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
25 }
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
26 \end{definition}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
27 \end{frame}
44
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
28 }
39
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
29
44
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
30 \defineUnit{binomialkoeffizient}{%
39
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
31 \begin{frame}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
32 \frametitle{Binomialkoeffizient}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
33 \setbeamercovered{dynamic}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
34
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
35 \begin{definition}[Binomialkoeffizient]
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
36 Der \structure{Binomialkoeffizient $\binom{n}{k}$} gibt die Anzahl der $k$-elementigen Teilmengen einer $n$-elementigen Menge an.
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
37 \begin{align}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
38 \binom{n}{k} = \frac{n!}{k!(n-k)!} = \frac{n^{\underline k}}{k!}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
39 \end{align}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
40 Man sagt \structure{n über k} oder \structure{k aus n}.
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
41 \end{definition}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
42 \begin{itemize}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
43 \item $\binom{n}{k}$ viele Möglichkeiten, $k$ Elemente aus $n$ Elementen zu wählen
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
44 \end{itemize}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
45
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
46 \vfill
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
47
44
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
48 \begin{theorem}[Pascalsche Identität]
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
49 Die \structure{Pascalsche Identität} liefert eine rekursive Definition des Binomialkoeffizienten.
41
0543f5ebd793 consistency
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 40
diff changeset
50 \begin{align}
44
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
51 \binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}
41
0543f5ebd793 consistency
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 40
diff changeset
52 \end{align}
44
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
53 \end{theorem}
39
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
54 \end{frame}
44
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
55 }
39
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
56
44
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
57 \defineUnit{multimengen}{%
39
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
58 \begin{frame}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
59 \frametitle{Multimengen}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
60 \setbeamercovered{dynamic}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
61
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
62 \begin{definition}[Multimenge]
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
63 \structure{Multimengen} sind eine Verallgemeinerung gewöhnlicher Mengen.\\
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
64 Elemente können nun mehrfach vorkommen, die Reihenfolge spielt weiterhin keine Rolle.\\
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
65 Sie werden meist auch mit $\left\{ \cdot \right\}$ notiert, alternativ $\{\!\vert \cdot \vert\!\}$.
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
66 \end{definition}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
67
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
68 \begin{theorem}[Anzahl von Multiteilmengen]
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
69 Eine \structure{$k$-Multiteilmenge} von $M$ mit $\abs{M} = n$ ist eine Multimenge, die $k$ (nicht unbedingt verschiedene) Elemente aus $M$ enthält.\\
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
70 Es gibt
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
71 \begin{align}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
72 \structure{\binom{k + n - 1}{k}} = \binom{k + n - 1}{n - 1}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
73 \end{align}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
74 solche Multiteilmengen.
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
75 \end{theorem}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
76
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
77 \begin{example}[]
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
78 \begin{itemize}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
79 \item $M \defeq \left\{ 1, 2, 2, 2, 3 \right\} = \left\{ 2, 1, 2, 3, 2 \right\} \qquad \abs{M} = 5$
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
80 \end{itemize}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
81 \end{example}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
82 \end{frame}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
83 }
44
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
84 }
39
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
85
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
86 \defineUnit{doppeltesabzaehlen}{%
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
87 \begin{frame}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
88 \frametitle{Doppeltes Abzählen}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
89 \setbeamercovered{dynamic}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
90
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
91 \begin{block}{Doppeltes Abzählen}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
92 Ermittelt man die \structure{Mächtigkeit} einer Menge auf zwei Arten, so müssen beide Ergebnisse \structure{übereinstimmen}.\\
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
93 Eine so ermittelte Gleichung kann die gesuchte Mächtigkeit festlegen.
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
94 \end{block}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
95
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
96 \begin{example}[Matrizen]
43
7245dcccf68d grammar; typo
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 42
diff changeset
97 In einer Matrix müssen die Summen von Zeilensummen und Spaltensummen übereinstimmen.
39
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
98 \end{example}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
99
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
100 \begin{example}[Studenten]
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
101 In einer Vorlesung sitzen \structure{64 Studenten} und \alert{n Studentinnen}.\\
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
102 Jeder Student kennt genau \structure{5} Studentinnen und jede Studentin \alert{8}~Studenten.
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
103 Wenn \enquote{bekannt sein} symmetrisch ist, wie viele Studentinnen besuchen die Vorlesung?
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
104 {
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
105 \setlength{\belowdisplayskip}{0pt}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
106 \begin{align}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
107 \structure{64 \cdot 5} &= \alert{n \cdot 8}\\
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
108 n &= \frac{64 \cdot 5}{8} = 40
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
109 \end{align}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
110 }
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
111 \end{example}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
112 \end{frame}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
113 }
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
114
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
115 \defineUnit{schubfachprinzip}{%
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
116 \begin{frame}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
117 \frametitle{Schubfachprinzip}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
118 \setbeamercovered{dynamic}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
119
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
120 \begin{definition}[Schubfachprinzip]
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
121 Sei $f : X \to Y$ eine Abbildung und $\abs{X} > \abs{Y}$.\\
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
122 Dann gilt
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
123 \begin{align}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
124 \exists y \in Y.\, \abs{f^{-1}(y)} \geq \alert{2}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
125 \end{align}
43
7245dcccf68d grammar; typo
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 42
diff changeset
126 Wenn man \structure{n} Elemente auf \structure{m < n} Fächer verteilt, dann gibt es \structure{mindestens ein Fach}, das mindestens \structure{2} Elemente enthält.
39
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
127 \end{definition}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
128
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
129 \vfill
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
130
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
131 \begin{definition}[Verallgemeinertes Schubfachprinzip]
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
132 Sei $f : X \to Y$ eine Abbildung und $\abs{X} > \abs{Y}$.\\
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
133 Dann gilt
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
134 \begin{align}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
135 \exists y \in Y.\, \abs{f^{-1}(y)} \geq \alert{\left \lceil \frac{\abs{X}}{\abs{Y}}\right \rceil}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
136 \end{align}
43
7245dcccf68d grammar; typo
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 42
diff changeset
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.
39
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
138 \end{definition}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
139 \end{frame}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
140 }
44
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
141
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
142 \defineUnit{inklusionexklusion}{%
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
143 \begin{frame}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
144 \frametitle{Inklusion und Exklusion}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
145 \setbeamercovered{dynamic}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
146
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
147 \begin{block}{Inklusion und Exklusion}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
148 Das Prinzip der \structure{Inklusion und Exklusion} erweitert die Summenregel um \alert{nicht disjunkte} Mengen.\\
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
149 Für drei Mengen $A, B, C$ gilt
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
150 \begin{align}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
151 \abs{A \cup B \cup C} = \abs{A} &\structure{+} \abs{B} \structure{+} \abs{C}\\
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
152 &\alert{-} \abs{A \cap B} \alert{-} \abs{A \cap C} \alert{-} \abs{B \cap C}\\
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
153 &\structure{+} \abs{A \cap B \cap C}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
154 \end{align}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
155 \end{block}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
156 \vfill
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
157 \begin{center}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
158 \begin{tikzpicture}[x=2em, y=2em]
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
159 \tikzstyle{opa} = [fill opacity=0.5]
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
160 \tikzstyle{A} = [tumred, fill=tumred!35, opa]
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
161 \tikzstyle{B} = [tumblue, fill=tumblue!35, opa]
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
162 \tikzstyle{C} = [tumgreen, fill=tumgreen!35, opa]
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
163 \draw[A] (-2, 0) ellipse (3 and 2);
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
164 \draw[B] (2, 0) ellipse (3 and 2);
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
165 \draw[C] (0, 2) ellipse (3 and 2);
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
166
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
167 \draw
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
168 (-3.5, -.5) node[tumred] {A}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
169 (3.5, -.5) node[tumblue] {B}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
170 (0, 3.5) node[tumgreen] {C}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
171 (-2, -.5) node {1}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
172 (2, -.5) node {1}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
173 (0, 2.5) node {1}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
174 (-1.5, 1) node {2}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
175 (1.5, 1) node {2}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
176 (0, -.5) node {2}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
177 (0, .75) node {3};
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
178 \end{tikzpicture}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
179 \end{center}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
180 \end{frame}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
181 }
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
182
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
183 \defineUnit{stirlingzahlen}{%
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
184 \begin{frame}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
185 \frametitle{Mengenpartition}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
186 \setbeamercovered{dynamic}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
187
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
188 \begin{definition}[$k$-Partition]
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
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
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
190 \begin{align}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
191 \biguplus_{i=1}^k A_i = A
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
192 \end{align}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
193 Dabei bezeichnet $\uplus$ die disjunkte Vereinigung.
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
194 \end{definition}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
195
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
196 \vfill
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
197
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
198 \begin{example}[]
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
199 Einige mögliche \structure{$3$-Partitionen} von $[5]$ sind
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
200 \begin{align}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
201 \left\{ \left\{ 1,2 \right\}, \left\{ 3,4 \right\}, \left\{ 5 \right\} \right\} &&&
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
202 \left\{ \left\{ 1 \right\}, \left\{ 3,4 \right\}, \left\{ 2, 5 \right\} \right\}\\
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
203 \left\{ \left\{ 1,2,3 \right\}, \left\{ 4 \right\}, \left\{ 5 \right\} \right\} &&&
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
204 \left\{ \left\{ 1, 5 \right\}, \left\{ 2, 4 \right\}, \left\{ 3 \right\} \right\}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
205 \end{align}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
206 Es existieren genau 25 solche $3$-Partitionen.
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
207 \end{example}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
208 \end{frame}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
209
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
210 \begin{frame}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
211 \frametitle{Stirlingzahlen zweiter Art}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
212 \setbeamercovered{dynamic}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
213
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
214 \begin{definition}[Stirlingzahlen zweiter Art]
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
215 Die \structure{Stirlingzahlen zweiter Art $S_{n, k}$} gibt die Anzahl der $k$-Partitoinen einer $n$-elementigen Menge an.
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
216 Wir schreiben
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
217 \begin{align}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
218 \stirlingtwo{n}{k} &\defeq S_{n, k}\\
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
219 \intertext{Es ist}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
220 \stirlingtwo{n}{k} &= \stirlingtwo{n-1}{k-1} + k \cdot \stirlingtwo{n-1}{k}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
221 \end{align}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
222 \end{definition}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
223 \begin{itemize}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
224 \item $\stirlingtwo{n}{k}$ viele Möglichkeiten, $n$ unterscheidbare Objekte in $k$ gleiche Fächer zu verteilen, sodass jedes Fach ein Objekt bekommt
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
225 \end{itemize}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
226
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
227 \vfill
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
228
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
229 \begin{example}[]
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
230 \begin{itemize}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
231 \item Es gibt $\stirlingtwo{5}{3} = 25$ $3$-Partitionen von $[5]$.
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
232 \end{itemize}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
233 \end{example}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
234 \end{frame}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
235
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
236 \begin{frame}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
237 \frametitle{Permutationen}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
238 \setbeamercovered{dynamic}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
239
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
240 \begin{definition}[Permutation]
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
241 Eine \structure{Permutation} einer Menge $A = \left\{ a_1, \dots, a_n \right\}$ ist eine \alert{bijektive Abbildung} $\pi : A \to A$.\\
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
242 Wir notieren Permutationen in zweizeiligen Vektoren.
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
243 \begin{align}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
244 \pi = \begin{pmatrix}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
245 a_1 & \dots & a_n \\
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
246 \pi(a_1) & \dots & \pi(a_n)
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
247 \end{pmatrix}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
248 \end{align}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
249 \end{definition}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
250 \begin{itemize}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
251 \item Weist jedem Element in $A$ ein neues, eindeutiges Element in $A$ zu.
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
252 \item \enquote{Mischt} die Elemente einer Menge
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
253 \end{itemize}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
254
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
255 \vfill
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
256
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
257 \begin{example}[]
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
258 $\pi$ ist eine Permutation auf $[9]$.
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
259 \begin{align}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
260 \pi = \begin{pmatrix}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
261 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
262 3 & 5 & 4 & 7 & 2 & 6 & 1 & 9 & 8
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
263 \end{pmatrix}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
264 \end{align}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
265 Es ist $\pi(1) = 3$, $\pi(4) = 7$.
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
266 \end{example}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
267 \end{frame}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
268
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
269 \begin{frame}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
270 \frametitle{Zyklus}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
271 \setbeamercovered{dynamic}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
272
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
273 \begin{definition}[$k$-Zyklus]
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
274 Ein \structure{$k$-Zyklus} ist eine Permutation $\pi$, die $k$ verschiedene Zahlen $i_1, \dots, i_k$ im Kreis vertauscht.
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
275 \begin{align}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
276 \pi &= \begin{pmatrix}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
277 i_1 & i_2 & \dots & i_k \\
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
278 i_2 & i_3 & \dots & i_1
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
279 \end{pmatrix} \\
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
280 \intertext{Wir schreiben auch}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
281 \pi &= \begin{pmatrix}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
282 i_1 & i_2 & \dots & i_k
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
283 \end{pmatrix}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
284 \end{align}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
285 Jede Permutation ist eine Verkettung disjunkter Zyklen.
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
286 \end{definition}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
287
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
288 \vfill
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
289
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
290 \begin{example}[]
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
291 % This is ugly :/
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
292 \vspace{-1em}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
293 \begin{align}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
294 \pi &= \begin{pmatrix}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
295 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
296 3 & 5 & 4 & 7 & 2 & 6 & 1 & 9 & 8
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
297 \end{pmatrix} \\
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
298 \intertext{$\pi$ enthält vier Zyklen.}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
299 \pi &= \begin{pmatrix}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
300 1 & 3 & 4 & 7
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
301 \end{pmatrix} \begin{pmatrix}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
302 2 & 5
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
303 \end{pmatrix} \begin{pmatrix}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
304 6
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
305 \end{pmatrix} \begin{pmatrix}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
306 8 & 9
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
307 \end{pmatrix}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
308 \end{align}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
309 \end{example}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
310 \end{frame}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
311
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
312 \begin{frame}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
313 \frametitle{Stirlingzahlen erster Art}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
314 \setbeamercovered{dynamic}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
315
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
316 \begin{definition}[Stirlingzahlen erster Art]
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
317 Die \structure{Stirlingzahlen erster Art $s_{n, k}$} gibt die Anzahl der Permutationen mit $n$ Elementen und \alert{k Zyklen} an.
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
318 Wir schreiben
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
319 \begin{align}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
320 \stirlingone{n}{k} &\defeq s_{n, k}\\
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
321 \intertext{Es ist}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
322 \stirlingone{n}{k} &= \stirlingone{n-1}{k-1} + (n-1) \cdot \stirlingone{n-1}{k}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
323 \end{align}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
324 \end{definition}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
325
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
326 \begin{itemize}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
327 \item Es gilt $\sum_{k=1}^n \stirlingone{n}{k} = n!$
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
328 \end{itemize}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
329
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
330 \vfill
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
331
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
332 \begin{example}[]
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
333 \begin{itemize}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
334 \item Es gibt $\stirlingone{9}{4} = 67284$ Permutationen über $[9]$ mit \alert{vier Zyklen}.
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
335 \end{itemize}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
336 \end{example}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
337 \end{frame}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
338 }