Mercurial > 13ws.ds

annotate notes/tex/combinatorics.tex @ 45:e65f4b1a6e32

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
remove fairly useless setbeamercovered
author Markus Kaiser <markus.kaiser@in.tum.de>
date Wed, 08 Jan 2014 14:26:02 +0100
parents 5734c1faf9cd
children f481e19e1430
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
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
5 \begin{definition}[Fakultät]
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
6 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
7 \[ 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
8 mit $0! \defeq 1$.
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
9 \end{definition}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
10
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
11 \vfill
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
12
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
13 \begin{definition}[Steigende und fallende Faktorielle]
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
14 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
15 {
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
16 \setlength{\belowdisplayskip}{0pt}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
17 \begin{align}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
18 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
19 &= 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
20 \intertext{\vspace{1em}}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
21 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
22 &= 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
23 \end{align}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
24 }
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
25 \end{definition}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
26 \end{frame}
44
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
27 }
39
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
28
44
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
29 \defineUnit{binomialkoeffizient}{%
39
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
30 \begin{frame}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
31 \frametitle{Binomialkoeffizient}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
32
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
33 \begin{definition}[Binomialkoeffizient]
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
34 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
35 \begin{align}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
36 \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
37 \end{align}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
38 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
39 \end{definition}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
40 \begin{itemize}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
41 \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
42 \end{itemize}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
43
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
44 \vfill
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
45
44
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
46 \begin{theorem}[Pascalsche Identität]
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
47 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
48 \begin{align}
44
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
49 \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
50 \end{align}
44
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
51 \end{theorem}
39
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
52 \end{frame}
44
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
53 }
39
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
54
44
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
55 \defineUnit{multimengen}{%
39
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
56 \begin{frame}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
57 \frametitle{Multimengen}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
58
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
59 \begin{definition}[Multimenge]
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
60 \structure{Multimengen} sind eine Verallgemeinerung gewöhnlicher Mengen.\\
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
61 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
62 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
63 \end{definition}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
64
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
65 \begin{theorem}[Anzahl von Multiteilmengen]
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
66 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
67 Es gibt
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
68 \begin{align}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
69 \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
70 \end{align}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
71 solche Multiteilmengen.
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
72 \end{theorem}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
73
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
74 \begin{example}[]
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
75 \begin{itemize}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
76 \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
77 \end{itemize}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
78 \end{example}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
79 \end{frame}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
80 }
44
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
81 }
39
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
82
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
83 \defineUnit{doppeltesabzaehlen}{%
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
84 \begin{frame}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
85 \frametitle{Doppeltes Abzählen}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
86
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
87 \begin{block}{Doppeltes Abzählen}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
88 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
89 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
90 \end{block}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
91
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
92 \begin{example}[Matrizen]
43
7245dcccf68d grammar; typo
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 42
diff changeset
93 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
94 \end{example}
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}[Studenten]
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
97 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
98 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
99 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
100 {
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
101 \setlength{\belowdisplayskip}{0pt}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
102 \begin{align}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
103 \structure{64 \cdot 5} &= \alert{n \cdot 8}\\
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
104 n &= \frac{64 \cdot 5}{8} = 40
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
105 \end{align}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
106 }
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
107 \end{example}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
108 \end{frame}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
109 }
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 \defineUnit{schubfachprinzip}{%
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
112 \begin{frame}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
113 \frametitle{Schubfachprinzip}
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 \begin{definition}[Schubfachprinzip]
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
116 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
117 Dann gilt
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
118 \begin{align}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
119 \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
120 \end{align}
43
7245dcccf68d grammar; typo
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 42
diff changeset
121 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
122 \end{definition}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
123
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
124 \vfill
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
125
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
126 \begin{definition}[Verallgemeinertes Schubfachprinzip]
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
127 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
128 Dann gilt
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
129 \begin{align}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
130 \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
131 \end{align}
43
7245dcccf68d grammar; typo
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 42
diff changeset
132 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
133 \end{definition}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
134 \end{frame}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
135 }
44
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
136
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
137 \defineUnit{inklusionexklusion}{%
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
138 \begin{frame}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
139 \frametitle{Inklusion und Exklusion}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
140
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
141 \begin{block}{Inklusion und Exklusion}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
142 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
143 Für drei Mengen $A, B, C$ gilt
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
144 \begin{align}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
145 \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
146 &\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
147 &\structure{+} \abs{A \cap B \cap C}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
148 \end{align}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
149 \end{block}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
150 \vfill
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
151 \begin{center}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
152 \begin{tikzpicture}[x=2em, y=2em]
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
153 \tikzstyle{opa} = [fill opacity=0.5]
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
154 \tikzstyle{A} = [tumred, fill=tumred!35, opa]
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
155 \tikzstyle{B} = [tumblue, fill=tumblue!35, opa]
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
156 \tikzstyle{C} = [tumgreen, fill=tumgreen!35, opa]
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
157 \draw[A] (-2, 0) ellipse (3 and 2);
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
158 \draw[B] (2, 0) ellipse (3 and 2);
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
159 \draw[C] (0, 2) ellipse (3 and 2);
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
160
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
161 \draw
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
162 (-3.5, -.5) node[tumred] {A}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
163 (3.5, -.5) node[tumblue] {B}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
164 (0, 3.5) node[tumgreen] {C}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
165 (-2, -.5) node {1}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
166 (2, -.5) node {1}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
167 (0, 2.5) node {1}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
168 (-1.5, 1) node {2}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
169 (1.5, 1) node {2}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
170 (0, -.5) node {2}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
171 (0, .75) node {3};
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
172 \end{tikzpicture}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
173 \end{center}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
174 \end{frame}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
175 }
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
176
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
177 \defineUnit{stirlingzahlen}{%
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
178 \begin{frame}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
179 \frametitle{Mengenpartition}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
180
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
181 \begin{definition}[$k$-Partition]
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
182 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
183 \begin{align}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
184 \biguplus_{i=1}^k A_i = A
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
185 \end{align}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
186 Dabei bezeichnet $\uplus$ die disjunkte Vereinigung.
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
187 \end{definition}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
188
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
189 \vfill
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
190
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
191 \begin{example}[]
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
192 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
193 \begin{align}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
194 \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
195 \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
196 \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
197 \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
198 \end{align}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
199 Es existieren genau 25 solche $3$-Partitionen.
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
200 \end{example}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
201 \end{frame}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
202
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
203 \begin{frame}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
204 \frametitle{Stirlingzahlen zweiter Art}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
205
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
206 \begin{definition}[Stirlingzahlen zweiter Art]
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
207 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
208 Wir schreiben
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
209 \begin{align}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
210 \stirlingtwo{n}{k} &\defeq S_{n, k}\\
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
211 \intertext{Es ist}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
212 \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
213 \end{align}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
214 \end{definition}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
215 \begin{itemize}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
216 \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
217 \end{itemize}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
218
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
219 \vfill
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
220
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
221 \begin{example}[]
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
222 \begin{itemize}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
223 \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
224 \end{itemize}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
225 \end{example}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
226 \end{frame}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
227
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
228 \begin{frame}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
229 \frametitle{Permutationen}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
230
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
231 \begin{definition}[Permutation]
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
232 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
233 Wir notieren Permutationen in zweizeiligen Vektoren.
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
234 \begin{align}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
235 \pi = \begin{pmatrix}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
236 a_1 & \dots & a_n \\
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
237 \pi(a_1) & \dots & \pi(a_n)
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
238 \end{pmatrix}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
239 \end{align}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
240 \end{definition}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
241 \begin{itemize}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
242 \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
243 \item \enquote{Mischt} die Elemente einer Menge
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
244 \end{itemize}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
245
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
246 \vfill
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
247
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
248 \begin{example}[]
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
249 $\pi$ ist eine Permutation auf $[9]$.
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
250 \begin{align}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
251 \pi = \begin{pmatrix}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
252 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
253 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
254 \end{pmatrix}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
255 \end{align}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
256 Es ist $\pi(1) = 3$, $\pi(4) = 7$.
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
257 \end{example}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
258 \end{frame}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
259
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
260 \begin{frame}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
261 \frametitle{Zyklus}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
262
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
263 \begin{definition}[$k$-Zyklus]
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
264 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
265 \begin{align}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
266 \pi &= \begin{pmatrix}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
267 i_1 & i_2 & \dots & i_k \\
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
268 i_2 & i_3 & \dots & i_1
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
269 \end{pmatrix} \\
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
270 \intertext{Wir schreiben auch}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
271 \pi &= \begin{pmatrix}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
272 i_1 & i_2 & \dots & i_k
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
273 \end{pmatrix}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
274 \end{align}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
275 Jede Permutation ist eine Verkettung disjunkter Zyklen.
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
276 \end{definition}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
277
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
278 \vfill
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
279
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
280 \begin{example}[]
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
281 % This is ugly :/
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
282 \vspace{-1em}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
283 \begin{align}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
284 \pi &= \begin{pmatrix}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
285 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
286 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
287 \end{pmatrix} \\
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
288 \intertext{$\pi$ enthält vier Zyklen.}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
289 \pi &= \begin{pmatrix}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
290 1 & 3 & 4 & 7
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
291 \end{pmatrix} \begin{pmatrix}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
292 2 & 5
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
293 \end{pmatrix} \begin{pmatrix}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
294 6
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
295 \end{pmatrix} \begin{pmatrix}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
296 8 & 9
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 \end{align}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
299 \end{example}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
300 \end{frame}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
301
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
302 \begin{frame}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
303 \frametitle{Stirlingzahlen erster Art}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
304
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
305 \begin{definition}[Stirlingzahlen erster Art]
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
306 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
307 Wir schreiben
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
308 \begin{align}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
309 \stirlingone{n}{k} &\defeq s_{n, k}\\
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
310 \intertext{Es ist}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
311 \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
312 \end{align}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
313 \end{definition}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
314
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
315 \begin{itemize}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
316 \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
317 \end{itemize}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
318
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
319 \vfill
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
320
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
321 \begin{example}[]
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
322 \begin{itemize}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
323 \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
324 \end{itemize}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
325 \end{example}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
326 \end{frame}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
327 }