1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
|
\section{Mathe}
\subsection{ggT, kgV, erweiterter euklidischer Algorithmus}
\lstinputlisting{math/gcd-lcm.cpp}
\lstinputlisting{math/extendedEuclid.cpp}
\subsubsection{Multiplikatives Inverses von $x$ in $\mathbb{Z}/n\mathbb{Z}$}
Sei $0 \leq x < n$. Definiere $d := gcd(x, n)$.
\begin{description}
\item[Falls $d = 1$:] ~
\begin{itemize}[nosep]
\item Erweiterter euklidischer Algorithmus liefert $\alpha$ und $\beta$ mit $\alpha x + \beta n = 1$
\item Nach Kongruenz gilt $\alpha x + \beta n \equiv \alpha x \equiv 1 \mod n$
\item $x^{-1} :\equiv \alpha \mod n$
\end{itemize}
\item[Falls $d \neq 1$:] es existiert kein $x^{-1}$
\end{description}
\lstinputlisting{math/multInv.cpp}
\subsection{Primzahlsieb von Eratosthenes}
\lstinputlisting{math/primeSieve.cpp}
\subsubsection{Faktorisierung}
\lstinputlisting{math/factor.cpp}
\subsubsection{Mod-Exponent über $\mathbb{F}_p$}
\lstinputlisting{math/modExp.cpp}
\subsection{LGS über $\mathbb{F}_p$}
\lstinputlisting{math/lgsFp.cpp}
\subsection{Binomialkoeffizienten}
\lstinputlisting{math/binomial.cpp}
\subsection{Satz von \textsc{Sprague-Grundy}}
Weise jedem Zustand $X$ wie folgt eine \textsc{Grundy}-Zahl $g\left(X\right)$ zu:
\[
g\left(X\right) := \min\{ \mathbb{Z}_0^+ \textbackslash \{g\left(Y\right)~|~Y \text{ von } X \text{ aus direkt erreichbar}\}\}
\]
$X$ ist genau dann gewonnen, wenn $g\left(X\right) > 0$ ist.\\\\
Wenn man $k$ Spiele in den Zuständen $X_1, \ldots, X_k$ hat, dann ist die \textsc{Grundy}-Zahl des Gesamtzustandes $g\left(X_1\right) \oplus \ldots \oplus g\left(X_k\right)$.
\lstinputlisting{math/nimm.cpp}
\subsection{Maximales Teilfeld}
\lstinputlisting{math/maxTeilfeld.cpp}
Obiger Code findet kein maximales Teilfeld, das über das Ende hinausgeht. Dazu:
\begin{enumerate}
\item finde maximales Teilfeld, das nicht übers Ende geht
\item berechne minimales Teilfeld, das nicht über den Rand geht (analog)
\item nimm Maximum aus gefundenem Maximalem und Allem\textbackslash Minimalem
\end{enumerate}
\subsection{Kombinatorik}
\subsubsection{Berühmte Zahlen}
\begin{tabular}{|l|l|l|}
\hline
\textsc{Fibonacci}-Zahlen & $f(0) = 0 \quad f(1) = 1 \quad f(n+2) = f(n+1) + f(n)$ & Bem. \ref{bem:fibonacciMat}, \ref{bem:fibonacciGreedy}\\
\textsc{Catalan}-Zahlen & $C_0 = 1 \quad C_n = \sum\limits_{k = 0}^{n - 1} C_kC_{n - 1 - k} = \frac{1}{n + 1}{2n \choose n} = \frac{2(2n - 1)}{n+1} \cdot C_{n-1}$ & Bem. \ref{bem:catalanOverflow}, \ref{bem:catalanAnwendung}\\
\textsc{Euler}-Zahlen (I) & $\left\langle\begin{array}{c} n \\ 0\end{array}\right\rangle = \left\langle\begin{array}{c} n \\ n-1 \end{array}\right\rangle = 1 \quad \left\langle\begin{array}{c} n \\ k\end{array}\right\rangle = (k + 1)\left\langle\begin{array}{c} n-1 \\ k\end{array}\right\rangle + (n-k)\left\langle\begin{array}{c} n-1 \\ k-1\end{array}\right\rangle$ & Bem. \ref{bem:euler1}\\
\textsc{Euler}-Zahlen (II) & $\left\langle\left\langle\begin{array}{c}n\\0\end{array}\right\rangle\right\rangle = 1 \quad \left\langle\left\langle\begin{array}{c}n\\n\end{array}\right\rangle\right\rangle = 0 \quad \left\langle\left\langle\begin{array}{c}n\\k\end{array}\right\rangle\right\rangle = (k + 1)\left\langle\left\langle\begin{array}{c}n-1\\k\end{array}\right\rangle\right\rangle + (2n - k - 1)\left\langle\left\langle\begin{array}{c}n-1\\k-1\end{array}\right\rangle\right\rangle$ & Bem. \ref{bem:euler2}\\
\textsc{Stirling}-Zahlen (I) & $\left[\begin{array}{c}0\\0\end{array}\right] = 1 \quad \left[\begin{array}{c}n\\0\end{array}\right] = \left[\begin{array}{c}0\\n\end{array}\right] = 0 \quad \left[\begin{array}{c}n\\k\end{array}\right] = \left[\begin{array}{c}n-1\\k-1\end{array}\right] + (n-1)\left[\begin{array}{c}n-1\\k\end{array}\right]$ & Bem. \ref{bem:stirling1}\\
\textsc{Stirling}-Zahlen (II) & $\left\{\begin{array}{c}n\\1\end{array}\right\} = \left\{\begin{array}{c}n\\n\end{array}\right\} = 1 \quad \left\{\begin{array}{c}n\\k\end{array}\right\} = k\left\{\begin{array}{c}n-1\\k\end{array}\right\} + \left\{\begin{array}{c}n-1\\k-1\end{array}\right\}$ & Bem. \ref{bem:stirling2}\\
Integer-Partitions & $f(1,1) = 1 \quad f(n,k) = 0 \text{ für } k > n \quad f(n,k) = f(n-k,k) + f(n,k-1)$ & Bem. \ref{bem:integerPartitions}\\
\hline
\end{tabular}
\begin{bem}\label{bem:fibonacciMat}
$\left(\begin{array}{cc} 0 & 1 \\ 1 & 1\end{array}\right)^n \cdot \left(\begin{array}{c}0 \\ 1\end{array}\right) = \left(\begin{array}{c}f_n \\ f_{n+1}\end{array}\right)$
\end{bem}
\begin{bem}[\textsc{Zeckendorfs} Theorem]\label{bem:fibonacciGreedy}
Jede positive natürliche Zahl kann eindeutig als Summe einer oder mehrerer verschiedener \textsc{Fibonacci}-Zahlen geschrieben werden, sodass keine zwei aufeinanderfolgenden \textsc{Fibonacci}-Zahlen in der Summe vorkommen.
\emph{Lösung: } Greedy, nimm immer die größte \textsc{Fibonacci}-Zahl, die noch hineinpasst.
\end{bem}
\begin{bem}\label{bem:catalanOverflow}
\begin{itemize}
\item Die erste und dritte angegebene Formel sind relativ sicher gegen Overflows.
\item Die erste Formel kann auch zur Berechnung der \textsc{Catalan}-Zahlen bezüglich eines Moduls genutzt werden.
\end{itemize}
\end{bem}
\begin{bem}\label{bem:catalanAnwendung}
Die \textsc{Catalan}-Zahlen geben an: $C_n =$
\begin{itemize}
\item Anzahl der Binärbäume mit $n$ Knoten
\item Anzahl der validen Klammerausdrücke mit $n$ Klammerpaaren
\item Anzahl der korrekten Klammerungen von $n+1$ Faktoren
\item Anzahl der Möglichkeiten ein konvexes Polygon mit $n+2$ Ecken in Dreiecke zu zerlegen.
\item Anzahl der monotonen Pfade in einem $n \times n$-Gitter, die nicht die Diagonale kreuzen. (zwischen gegenüberliegenden Ecken)
\end{itemize}
\end{bem}
\begin{bem}[\textsc{Euler}-Zahlen 1. Ordnung]\label{bem:euler1}
Die Anzahl der Permutationen von $\{1, \ldots, n\}$ mit genau $k$ Anstiegen.
Begründung: Für die $n$-te Zahl gibt es $n$ mögliche Positionen zum Einfügen. Dabei wird entweder ein Ansteig in zwei gesplitted oder ein Anstieg um $n$ ergänzt.
\end{bem}
\begin{bem}[\textsc{Euler}-Zahlen 2. Ordnung]\label{bem:euler2}
Die Anzahl der Permutationen von $\{1,1, \ldots, n,n\}$ mit genau $k$ Anstiegen.
\end{bem}
\begin{bem}[\textsc{Stirling}-Zahlen 1. Ordnung]\label{bem:stirling1}
Die Anzahl der Permutationen von $\{1, \ldots, n\}$ mit genau $k$ Zyklen.
Begründung: Es gibt zwei Möglichkeiten für die $n$-te Zahl. Entweder sie bildet einen eigene Zyklus, oder sie kann an jeder Position in jedem Zyklus einsortiert werden.
\end{bem}
\begin{bem}[\textsc{Stirling}-Zahlen 2. Ordnung]\label{bem:stirling2}
Die Anzahl der Möglichkeiten $n$ Elemente in $k$ nichtleere Teilmengen zu zerlegen.
Begründung: Es gibt $k$ Möglichkeiten die $n$ in eine $n-1$-Partition einzuordnen. Dazu kommt der Fall, dass die $n$ in ihrer eigenen Teilmenge (alleine) steht.
\end{bem}
\begin{bem}\label{bem:integerPartitions}
Anzahl der Teilmengen von $\mathbb{N}$, die sich zu $n$ aufaddieren mit maximalem Elment $\leq k$.
\end{bem}
\subsubsection{Verschiedenes}
\begin{tabular}{|l|l|}
\hline
Hanoi Towers (min steps) & $T_n = 2^n - 1$\\
\#regions by $n$ lines & $n\left(n + 1\right) / 2 + 1$\\
\#bounded regions by $n$ lines & $\left(n^2 - 3n + 2\right) / 2$\\
\#labeled rooted trees & $n^{n-1}$\\
\#labeled unrooted trees & $n^{n-2}$\\
\hline
\end{tabular}
|
