Mercurial > 13ws.ds

annotate notes/tex/combinatorics.tex @ 47:e262c2969666

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
wording
author Markus Kaiser <markus.kaiser@in.tum.de>
date Wed, 08 Jan 2014 21:12:37 +0100
parents f481e19e1430
children
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 }
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
81
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
82 \defineUnit{doppeltesabzaehlen}{%
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
83 \begin{frame}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
84 \frametitle{Doppeltes Abzählen}
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 \begin{block}{Doppeltes Abzählen}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
87 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
88 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
89 \end{block}
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{example}[Matrizen]
43
7245dcccf68d grammar; typo
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 42
diff changeset
92 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
93 \end{example}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
94
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
95 \begin{example}[Studenten]
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
96 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
97 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
98 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
99 {
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
100 \setlength{\belowdisplayskip}{0pt}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
101 \begin{align}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
102 \structure{64 \cdot 5} &= \alert{n \cdot 8}\\
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
103 n &= \frac{64 \cdot 5}{8} = 40
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
104 \end{align}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
105 }
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
106 \end{example}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
107 \end{frame}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
108 }
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 \defineUnit{schubfachprinzip}{%
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
111 \begin{frame}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
112 \frametitle{Schubfachprinzip}
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 \begin{definition}[Schubfachprinzip]
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
115 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
116 Dann gilt
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
117 \begin{align}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
118 \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
119 \end{align}
43
7245dcccf68d grammar; typo
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 42
diff changeset
120 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
121 \end{definition}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
122
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
123 \vfill
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
124
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
125 \begin{definition}[Verallgemeinertes Schubfachprinzip]
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
126 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
127 Dann gilt
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
128 \begin{align}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
129 \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
130 \end{align}
43
7245dcccf68d grammar; typo
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 42
diff changeset
131 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
132 \end{definition}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
133 \end{frame}
0b7b90f84986 nineth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
134 }
44
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
135
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
136 \defineUnit{inklusionexklusion}{%
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
137 \begin{frame}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
138 \frametitle{Inklusion und Exklusion}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
139
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
140 \begin{block}{Inklusion und Exklusion}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
141 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
142 Für drei Mengen $A, B, C$ gilt
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
143 \begin{align}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
144 \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
145 &\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
146 &\structure{+} \abs{A \cap B \cap C}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
147 \end{align}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
148 \end{block}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
149 \vfill
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
150 \begin{center}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
151 \begin{tikzpicture}[x=2em, y=2em]
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
152 \tikzstyle{opa} = [fill opacity=0.5]
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
153 \tikzstyle{A} = [tumred, fill=tumred!35, opa]
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
154 \tikzstyle{B} = [tumblue, fill=tumblue!35, opa]
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
155 \tikzstyle{C} = [tumgreen, fill=tumgreen!35, opa]
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
156 \draw[A] (-2, 0) ellipse (3 and 2);
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
157 \draw[B] (2, 0) ellipse (3 and 2);
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
158 \draw[C] (0, 2) ellipse (3 and 2);
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
159
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
160 \draw
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
161 (-3.5, -.5) node[tumred] {A}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
162 (3.5, -.5) node[tumblue] {B}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
163 (0, 3.5) node[tumgreen] {C}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
164 (-2, -.5) node {1}
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 (0, 2.5) node {1}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
167 (-1.5, 1) node {2}
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 (0, -.5) node {2}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
170 (0, .75) node {3};
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
171 \end{tikzpicture}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
172 \end{center}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
173 \end{frame}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
174 }
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 \defineUnit{stirlingzahlen}{%
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
177 \begin{frame}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
178 \frametitle{Mengenpartition}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
179
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
180 \begin{definition}[$k$-Partition]
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
181 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
182 \begin{align}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
183 \biguplus_{i=1}^k A_i = A
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
184 \end{align}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
185 Dabei bezeichnet $\uplus$ die disjunkte Vereinigung.
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
186 \end{definition}
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 \vfill
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
189
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
190 \begin{example}[]
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
191 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
192 \begin{align}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
193 \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
194 \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
195 \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
196 \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
197 \end{align}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
198 Es existieren genau 25 solche $3$-Partitionen.
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
199 \end{example}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
200 \end{frame}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
201
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
202 \begin{frame}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
203 \frametitle{Stirlingzahlen zweiter Art}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
204
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
205 \begin{definition}[Stirlingzahlen zweiter Art]
47
e262c2969666 wording
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 46
diff changeset
206 Die \structure{Stirlingzahl zweiter Art $S_{n, k}$} gibt die Anzahl der $k$-Partitoinen einer $n$-elementigen Menge an.
44
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
207 Wir schreiben
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
208 \begin{align}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
209 \stirlingtwo{n}{k} &\defeq S_{n, k}\\
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
210 \intertext{Es ist}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
211 \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
212 \end{align}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
213 \end{definition}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
214 \begin{itemize}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
215 \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
216 \end{itemize}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
217
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
218 \vfill
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
219
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
220 \begin{example}[]
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
221 \begin{itemize}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
222 \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
223 \end{itemize}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
224 \end{example}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
225 \end{frame}
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 \begin{frame}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
228 \frametitle{Permutationen}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
229
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
230 \begin{definition}[Permutation]
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
231 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
232 Wir notieren Permutationen in zweizeiligen Vektoren.
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
233 \begin{align}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
234 \pi = \begin{pmatrix}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
235 a_1 & \dots & a_n \\
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
236 \pi(a_1) & \dots & \pi(a_n)
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
237 \end{pmatrix}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
238 \end{align}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
239 \end{definition}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
240 \begin{itemize}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
241 \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
242 \item \enquote{Mischt} die Elemente einer Menge
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
243 \end{itemize}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
244
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
245 \vfill
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
246
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
247 \begin{example}[]
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
248 $\pi$ ist eine Permutation auf $[9]$.
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
249 \begin{align}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
250 \pi = \begin{pmatrix}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
251 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
252 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
253 \end{pmatrix}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
254 \end{align}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
255 Es ist $\pi(1) = 3$, $\pi(4) = 7$.
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
256 \end{example}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
257 \end{frame}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
258
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
259 \begin{frame}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
260 \frametitle{Zyklus}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
261
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
262 \begin{definition}[$k$-Zyklus]
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
263 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
264 \begin{align}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
265 \pi &= \begin{pmatrix}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
266 i_1 & i_2 & \dots & i_k \\
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
267 i_2 & i_3 & \dots & i_1
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
268 \end{pmatrix} \\
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
269 \intertext{Wir schreiben auch}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
270 \pi &= \begin{pmatrix}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
271 i_1 & i_2 & \dots & i_k
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
272 \end{pmatrix}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
273 \end{align}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
274 Jede Permutation ist eine Verkettung disjunkter Zyklen.
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
275 \end{definition}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
276
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
277 \vfill
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
278
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
279 \begin{example}[]
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
280 % This is ugly :/
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
281 \vspace{-1em}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
282 \begin{align}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
283 \pi &= \begin{pmatrix}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
284 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
285 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
286 \end{pmatrix} \\
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
287 \intertext{$\pi$ enthält vier Zyklen.}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
288 \pi &= \begin{pmatrix}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
289 1 & 3 & 4 & 7
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
290 \end{pmatrix} \begin{pmatrix}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
291 2 & 5
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
292 \end{pmatrix} \begin{pmatrix}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
293 6
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
294 \end{pmatrix} \begin{pmatrix}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
295 8 & 9
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
296 \end{pmatrix}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
297 \end{align}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
298 \end{example}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
299 \end{frame}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
300
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
301 \begin{frame}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
302 \frametitle{Stirlingzahlen erster Art}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
303
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
304 \begin{definition}[Stirlingzahlen erster Art]
47
e262c2969666 wording
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 46
diff changeset
305 Die \structure{Stirlingzahl erster Art $s_{n, k}$} gibt die Anzahl der Permutationen mit $n$ Elementen und \alert{k Zyklen} an.
44
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
306 Wir schreiben
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
307 \begin{align}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
308 \stirlingone{n}{k} &\defeq s_{n, k}\\
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
309 \intertext{Es ist}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
310 \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
311 \end{align}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
312 \end{definition}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
313
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
314 \begin{itemize}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
315 \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
316 \end{itemize}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
317
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
318 \vfill
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
319
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
320 \begin{example}[]
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
321 \begin{itemize}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
322 \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
323 \end{itemize}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
324 \end{example}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
325 \end{frame}
5734c1faf9cd tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 43
diff changeset
326 }