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