\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 \textsc{Eratosthenes}}
\lstinputlisting{math/primeSieve.cpp}

\subsection{\textsc{Miller}-\textsc{Rabin}-Primzahltest}
\lstinputlisting{math/millerRabin.cpp}

\subsection{Faktorisierung}
\lstinputlisting{math/factor.cpp}

\subsection{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{Polynome \& FFT}
Multipliziert Polynome $A$ und $B$.
\begin{itemize}
	\item $\deg(A * B) = \deg(A) + \deg(B)$
	\item Vektoren \lstinline{a} und \lstinline{b} müssen mindestens Größe $\deg(A * B) + 1$ haben.
	Größe muss eine Zweierpotenz sein.
	\item Für ganzzahlige Koeffizienten: \lstinline{(int)round(real(a[i]))}
\end{itemize}
\lstinputlisting{math/fft.cpp}

\subsection{Kombinatorik}

\subsubsection{Berühmte Zahlen}
\begin{tabularx}{\textwidth}{|l|X|l|}
	\hline
	\textsc{Fibonacci}-Zahlen	&
	$f(0) = 0 \qquad
	f(1) = 1 \qquad
	f(n+2) = f(n+1) + f(n)$ &
	Bem. \ref{bem:fibonacciMat}, \ref{bem:fibonacciGreedy} \\

	\textsc{Catalan}-Zahlen	&
	$C_0 = 1 \qquad
	C_n = \sum\limits_{k = 0}^{n - 1} C_kC_{n - 1 - k} = \frac{1}{n + 1}\binom{2n}{n} = \frac{2(2n - 1)}{n+1} \cdot C_{n-1}$ &
	Bem. \ref{bem:catalanOverflow}, \ref{bem:catalanAnwendung} \\

	\textsc{Euler}-Zahlen (I) &
	$\eulerI{n}{0} = \eulerI{n}{n-1} = 1 \qquad
	\eulerI{n}{k} = (k+1) \eulerI{n-1}{k} + (n-k) \eulerI{n-1}{k-1} $ &
	Bem. \ref{bem:euler1} \\

	\textsc{Euler}-Zahlen (II) &
	$\eulerII{n}{0} = 1 \qquad
	\eulerII{n}{n} = 0 \qquad
	\eulerII{n}{k} = (k+1) \eulerII{n-1}{k} + (2n-k-1) \eulerII{n-1}{k-1}$ &
	Bem. \ref{bem:euler2} \\

	\textsc{Stirling}-Zahlen (I) &
	$\stirlingI{0}{0} = 1 \qquad
	\stirlingI{n}{0} = \stirlingI{0}{n} = 0 \qquad
	\stirlingI{n}{k} = \stirlingI{n-1}{k-1} + (n-1) \stirlingI{n-1}{k}$ &
	Bem. \ref{bem:stirling1} \\

	\textsc{Stirling}-Zahlen (II) &
	$\stirlingII{n}{1} = \stirlingII{n}{n} = 1 \qquad
	\stirlingII{n}{k} = k \stirlingII{n-1}{k} + \stirlingII{n-1}{k-1}$ &
	Bem. \ref{bem:stirling2} \\

	Integer-Partitions &
	$f(1,1) = 1 \qquad f(n,k) = 0 \text{ für } k > n \qquad f(n,k)  = f(n-k,k) + f(n,k-1)$ &
	Bem. \ref{bem:integerPartitions} \\
	\hline
\end{tabularx}

\begin{bem}\label{bem:fibonacciMat}
$
\begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}^n
\cdot
\begin{pmatrix} 0 \\ 1 \end{pmatrix}
=
\begin{pmatrix}f_n \\ f_{n+1} \end{pmatrix}
$
\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}

\subsection{3D-Kugeln}
\lstinputlisting{math/gcDist.cpp}