path: root/math/math.tex

\section{Mathe}

\subsection{ggT, kgV, erweiterter euklidischer Algorithmus}
\lstinputlisting{math/gcd-lcm.cpp}
\lstinputlisting{math/extendedEuclid.cpp}

\paragraph{Lemma von \textsc{Bézout}}
Sei $(x, y)$ eine Lösung für $ax + by = d$.
Dann lassen sich wie folgt alle Lösungen berechnen:
\[
	\left(x + k\frac{b}{\ggT(a, b)},~y - k\frac{a}{\ggT(a, b)}\right)
\]

\paragraph{Multiplikatives Inverses von $x$ in $\mathbb{Z}/n\mathbb{Z}$}
Sei $0 \leq x < n$. Definiere $d := \ggT(x, n)$.\newline
\textbf{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}
\textbf{Falls $d \neq 1$:} Es existiert kein $x^{-1}$.
\lstinputlisting{math/multInv.cpp}

\subsection{Mod-Exponent über $\mathbb{F}_p$}
\lstinputlisting{math/modExp.cpp}

\subsection{Chinesischer Restsatz}
\begin{itemize}
	\item Extrem anfällig gegen Overflows. Evtl. häufig 128-Bit Integer verwenden.
	\item Direkte Formel für zwei Kongruenzen $x \equiv a \mod n$, $x \equiv b \mod m$:
	\[
		x \equiv a - y * n * \frac{a - b}{d} \mod \frac{mn}{d}
		\qquad \text{mit} \qquad
		d := \ggT(n, m) = yn + zm
	\]
	Formel kann auch für nicht teilerfremde Moduli verwendet werden.
	Sind die Moduli nicht teilerfremd, existiert genau dann eine Lösung,
	wenn $a_i \equiv a_j \mod \ggT(m_i, m_j)$.
	In diesem Fall sind keine Faktoren
	auf der linken Seite erlaubt.
\end{itemize}
\lstinputlisting{math/chineseRemainder.cpp}

\subsection{Primzahltest \& Faktorisierung}
\lstinputlisting{math/primes.cpp}

\subsection{Primzahlsieb von \textsc{Eratosthenes}}
\lstinputlisting{math/primeSieve.cpp}

\subsection{\textsc{Euler}sche $\varphi$-Funktion}
\begin{itemize}[nosep]
	\item Zählt die relativ primen Zahlen $\leq n$.

	\item Multiplikativ:
	$\gcd(a,b) = 1 \Longrightarrow \varphi(a) \cdot \varphi(b) = \varphi(ab)$

	\item $p$ prim, $k \in \mathbb{N}$:
	$~\varphi(p^k) = p^k - p^{k - 1}$

	\item $n = p_1^{a_1} \cdot \ldots \cdot p_k^{a_k}$:
	$~\varphi(n) = n \cdot \left(1 - \frac{1}{p_1}\right) \cdot \ldots \cdot \left(1 - \frac{1}{p_k}\right)$
	Evtl. ist es sinnvoll obgien Code zum Faktorisieren zu benutzen und dann diese Formel anzuwenden.

	\item \textbf{\textsc{Euler}'s Theorem:}
	Seien $a$ und $m$ teilerfremd. Dann:
	$a^{\varphi(m)} \equiv 1 \mod m$\newline
	Falls $m$ prim ist, liefert das den \textbf{kleinen Satz von \textsc{Fermat}}:
	$a^{m} \equiv a \mod m$
\end{itemize}
\lstinputlisting{math/phi.cpp}

\subsection{Primitivwurzeln}
\begin{itemize}[nosep]
	\item Primitivwurzel modulo $n$ existiert genau dann wenn:
	\begin{itemize}[nosep]
		\item $n$ ist $1$, $2$ oder $4$, oder
		\item $n$ ist Potenz einer ungeraden Primzahl, oder
		\item $n$ ist das Doppelte einer Potenz einer ungeraden Primzahl.
	\end{itemize}

	\item Sei $g$ Primitivwurzel modulo $n$.
	Dann gilt:\newline
	Das kleinste $k$, sodass $g^k \equiv 1 \mod n$, ist $k = \varphi(n)$.
\end{itemize}
\lstinputlisting{math/primitiveRoot.cpp}

\subsection{Diskreter Logarithmus}
\lstinputlisting{math/discreteLogarithm.cpp}

\subsection{Binomialkoeffizienten}
\lstinputlisting{math/binomial.cpp}

\subsection{LGS über $\mathbb{F}_p$}
\lstinputlisting{math/lgsFp.cpp}

\subsection{LGS über $\mathbb{R}$}
\lstinputlisting{math/gauss.cpp}

\subsection{Polynome \& FFT}
Multipliziert Polynome $A$ und $B$.
\begin{itemize}[nosep]
	\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{3D-Kugeln}
\lstinputlisting{math/spheres.cpp}

\subsection{Longest Increasing Subsequence}
\lstinputlisting{math/longestIncreasingSubsequence.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\left\{
		\mathbb{Z}_0^+ \setminus
		\left\{g\left(Y\right) \mid Y \text{ von } X \text{ aus direkt erreichbar}\right\}
	\right\} 
\]
$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)$.

\subsection{\textsc{Legendre}-Symbol}
Sei $p \geq 3$ eine Primzahl, $a \in \mathbb{Z}$:
\begin{align*}
	\legendre{a}{p} &=
	\begin{cases*}
		 0 & falls $p~\vert~a$ \\[-1ex]
		 1 & falls $\exists x \in \mathbb{Z}\backslash p\mathbb{Z} : a \equiv x^2 \mod p$ \\[-1ex]
		-1 & sonst
	\end{cases*} \\
	\legendre{-1}{p} &= (-1)^{\frac{p - 1}{2}} =
	\begin{cases*}
		 1 & falls $p \equiv 1 \mod 4$ \\[-1ex]
		-1 & falls $p \equiv 3 \mod 4$
	\end{cases*} \\
	\legendre{2}{p} &= (-1)^{\frac{p^2 - 1}{8}} =
	\begin{cases*}
		 1 & falls $p \equiv \pm 1 \mod 8$ \\[-1ex]
		-1 & falls $p \equiv \pm 3 \mod 8$
	\end{cases*} \\
	\legendre{p}{q} \cdot \legendre{q}{p} &=
	(-1)^{\frac{p - 1}{2} \cdot \frac{q - 1}{2}}
\end{align*}

\subsection{Kombinatorik}

\begin{flushleft}
	\begin{tabular}{ll}
		\toprule
		\multicolumn{2}{c}{Berühmte Zahlen} \\
		\midrule 
		\textsc{Fibonacci}	&
		$f(0) = 0 \quad
		f(1) = 1 \quad
		f(n+2) = f(n+1) + f(n)$ \\

		\textsc{Catalan}	&
		$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}$ \\

		\textsc{Euler} 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} $ \\

		\textsc{Euler} II &
		$\eulerII{n}{0} = 1 \quad
		\eulerII{n}{n} = 0 \quad
		\eulerII{n}{k} = (k+1) \eulerII{n-1}{k} + (2n-k-1) \eulerII{n-1}{k-1}$ \\

		\textsc{Stirling} 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}$ \\

		\textsc{Stirling} II &
		$\stirlingII{n}{1} = \stirlingII{n}{n} = 1 \qquad
		\stirlingII{n}{k} = k \stirlingII{n-1}{k} + \stirlingII{n-1}{k-1}$ \\

		\textsc{Bell} &
		$B_1 = 1 \qquad
		B_n = \sum\limits_{k = 0}^{n - 1} B_k\binom{n-1}{k}
		= \sum\limits_{k = 0}^{n}\stirlingII{n}{k}$\\

		\textsc{Int. 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)$ \\
		\bottomrule
	\end{tabular}
\end{flushleft}

\paragraph{\textsc{Zeckendorfs} Theorem}
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.

\paragraph{\textsc{Catalan}-Zahlen}
\begin{itemize}[nosep]
	\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.
	\item Die \textsc{Catalan}-Zahlen geben an: $C_n =$
	\begin{itemize}[nosep]
		\item Anzahl der Binärbäume mit $n$ nicht unterscheidbaren 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 (zwischen gegenüberliegenden Ecken) in
		einem $n \times n$-Gitter, die nicht die Diagonale kreuzen.
	\end{itemize}
\end{itemize}

\paragraph{\textsc{Euler}-Zahlen 1. Ordnung}
Die Anzahl der Permutationen von $\{1, \ldots, n\}$ mit genau $k$ Anstiegen.
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.

\paragraph{\textsc{Euler}-Zahlen 2. Ordnung}
Die Anzahl der Permutationen von $\{1,1, \ldots, n,n\}$ mit genau $k$ Anstiegen.

\paragraph{\textsc{Stirling}-Zahlen 1. Ordnung}
Die Anzahl der Permutationen von $\{1, \ldots, n\}$ mit genau $k$ Zyklen.
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.

\paragraph{\textsc{Stirling}-Zahlen 2. Ordnung}
Die Anzahl der Möglichkeiten $n$ Elemente in $k$ nichtleere Teilmengen zu zerlegen.
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.

\paragraph{\textsc{Bell}-Zahlen}
Anzahl der Partitionen von $\{1, \ldots, n\}$.
Wie \textsc{Striling}-Zahlen 2. Ordnung ohne Limit durch $k$.

\paragraph{Integer Partitions}
Anzahl der Teilmengen von $\mathbb{N}$, die sich zu $n$ aufaddieren mit maximalem Elment $\leq k$.\\

\begin{tabular}{lcr}
	\toprule
	\multicolumn{3}{c}{Binomialkoeffizienten} \\
	\midrule
	$\binom{n}{k} = \frac{n!}{k!(n - k)!}$ &
	$\binom{n}{k} = \binom{n - 1}{k} + \binom{n - 1}{k - 1}$ &
	$\sum\limits_{k = 0}^n\binom{r + k}{k} = \binom{r + n + 1}{n}$ \\

	$\sum\limits_{k = 0}^n \binom{n}{k} = 2^n$ &
	$\binom{n}{m}\binom{m}{k} = \binom{n}{k}\binom{n - k}{m - k}$ &
	$\binom{n}{k} = (-1)^k \binom{k - n - 1}{k}$ \\

	$\binom{n}{k} = \binom{n}{n - k}$ &
	$\sum\limits_{k = 0}^n \binom{k}{m} = \binom{n + 1}{m + 1}$ &
	$\sum\limits_{i = 0}^n \binom{n}{i}^2 = \binom{2n}{n}$ \\

	$\binom{n}{k} = \frac{n}{k}\binom{n - 1}{k - 1}$ &
	$\sum\limits_{k = 0}^n \binom{r}{k}\binom{s}{n - k} = \binom{r + s}{n}$ &
	$\sum\limits_{i = 1}^n \binom{n}{i} F_i = F_{2n} \quad F_n = n\text{-th Fib.}$ \\
	\bottomrule
\end{tabular}
\vspace{5mm}

\begin{tabular}{l|l|l}
	\toprule
	\multicolumn{3}{c}{Reihen} \\
	\midrule
	$\sum\limits_{i = 1}^n i = \frac{n(n+1)}{2}$ &
	$\sum\limits_{i = 1}^n i^2 = \frac{n(n + 1)(n + 2)}{6}$ & 
	$\sum\limits_{i = 1}^n i^3 = \frac{n^2 (n + 1)^2}{4}$ \\

	$\sum\limits_{i = 0}^n c^i = \frac{c^{n + 1} - 1}{c - 1} \quad c \neq 1$ &
	$\sum\limits_{i = 0}^\infty c^i = \frac{1}{1 - c} \quad \vert c \vert < 1$ &
	$\sum\limits_{i = 1}^\infty c^i = \frac{c}{1 - c} \quad \vert c \vert < 1$ \\

	\multicolumn{2}{l|}{
		$\sum\limits_{i = 0}^n ic^i = \frac{nc^{n + 2} - (n + 1)c^{n + 1} + c}{(c - 1)^2} \quad c \neq 1$
	} &
	$\sum\limits_{i = 0}^\infty ic^i = \frac{c}{(1 - c)^2} \quad \vert c \vert < 1$ \\

	$H_n = \sum\limits_{i = 1}^n \frac{1}{i}$ &
	\multicolumn{2}{l}{
		$\sum\limits_{i = 1}^n iH_i = \frac{n(n + 1)}{2}H_n - \frac{n(n - 1)}{4}$
	} \\

	$\sum\limits_{i = 1}^n H_i = (n + 1)H_n - n$ &
	\multicolumn{2}{l}{
		$\sum\limits_{i = 1}^n \binom{i}{m}H_i =
		\binom{n + 1}{m + 1} \left(H_{n + 1} - \frac{1}{m  + 1}\right)$
	} \\
	\bottomrule
\end{tabular}
\vspace{5mm}

\begin{tabular}{c|cccc}
	\toprule
	\multicolumn{5}{c}{The Twelvefold Way (verteile $n$ Bälle auf $k$ Boxen)} \\
	\midrule
	Bälle & identisch & unterscheidbar & identisch      & unterscheidbar \\
	Boxen & identisch & identisch      & unterscheidbar & unterscheidbar \\
	\midrule
	- &
	$p_k(n)$ &
	$\sum\limits_{i = 0}^k \stirlingII{n}{i}$ &
	$\binom{n + k - 1}{k - 1}$ &
	$k^n$ \\

	size $\geq 1$ &
	$p(n, k)$ &
	$\stirlingII{n}{k}$ &
	$\binom{n - 1}{k - 1}$ &
	$k! \stirlingII{n}{k}$ \\

	size $\leq 1$ &
	$[n \leq k]$ &
	$[n \leq k]$ &
	$\binom{k}{n}$ &
	$n! \binom{k}{n}$ \\
	\midrule
	\multicolumn{5}{l}{
		$p_k(n)$: \#Anzahl der Partitionen von $n$ in $\leq k$ positive Summanden.
	} \\
	\multicolumn{5}{l}{
		$p(n, k)$: \#Anzahl der Partitionen von $n$ in genau $k$ positive Summanden.
	} \\
	\multicolumn{5}{l}{
		$[\text{Bedingung}]$: \lstinline{return Bedingung ? 1 : 0;}
	} \\
	\bottomrule
\end{tabular}
\vspace{5mm}

\begin{tabular}{l|r}
	\toprule
	\multicolumn{2}{c}{
		Wahrscheinlichkeitstheorie ($A,B$ Ereignisse und $X,Y$ Variablen)
	} \\
	\midrule
	$\E(X + Y) = \E(X) + \E(Y)$ &
	$\E(\alpha X) = \alpha \E(X)$ \\

	$X, Y$ unabh. $\Leftrightarrow \E(XY) = \E(X) \cdot \E(Y)$ &
	$\Pr[A \vert B] = \frac{\Pr[A \land B]}{\Pr[B]}$ \\

	$\Pr[A \lor B] = \Pr[A] + \Pr[B] - \Pr[A \land B]$ &
	$\Pr[A \land B] = \Pr[A] \cdot \Pr[B]$ \\
	\bottomrule
\end{tabular}
\vspace{5mm}

\begin{tabular}{lr|lr}
	\toprule
	\multicolumn{4}{c}{\textsc{Bertrand}'s Ballot Theorem (Kandidaten $A$ und $B$, $k \in \mathbb{N}$)} \\
	\midrule
	$\#A > k\#B$ & $Pr = \frac{a - kb}{a + b}$ &
	$\#B - \#A \leq k$ & $Pr = 1 - \frac{a!b!}{(a + k + 1)!(b - k - 1)!}$ \\

	$\#A \geq k\#B$ & $Pr = \frac{a + 1 - kb}{a + 1}$ &
	$\#A \geq \#B + k$ & $Num = \frac{a - k + 1 - b}{a - k + 1} \binom{a + b - k}{b}$ \\
	\bottomrule
\end{tabular}
\vspace{5mm}

\begin{tabular}{ll}
	\toprule
	\multicolumn{2}{c}{Verschiedenes} \\
	\midrule
	Türme von Hanoi, minimale Schirttzahl: &
	$T_n = 2^n - 1$ \\

	\#Regionen zwischen $n$ Gearden	&
	$\frac{n\left(n + 1\right)}{2} + 1$ \\

	\#abgeschlossene Regionen zwischen $n$ Geraden &
	$\frac{n^2 - 3n + 2}{2}$ \\

	\#markierte, gewurzelte Bäume	&
	$n^{n-1}$ \\

	\#markierte, nicht gewurzelte Bäume	&
	$n^{n-2}$ \\

	\#Wälder mit $k$ gewurzelten Bäumen	&
	$\frac{k}{n}\binom{n}{k}n^{n-k}$ \\
	\bottomrule
\end{tabular}
\vspace{5mm}

\begin{flushleft}
	\begin{tabular}{l|cccl}
		\toprule
		\multicolumn{5}{c}{Platonische Körper} \\
		\midrule
		Übersicht       & Seiten & Ecken & Kanten & dual zu \\
		\midrule
		Tetraeder       & 4      & 4     & 6      & Tetraeder \\
		Würfel/Hexaeder & 6      & 8     & 12     & Oktaeder \\
		Oktaeder        & 8      & 6     & 12     & Würfel/Hexaeder\\
		Dodekaeder      & 12     & 20    & 30     & Ikosaeder \\
		Ikosaeder       & 20     & 12    & 30     & Dodekaeder \\
		\midrule
		\multicolumn{5}{c}{Färbungen mit maximal $n$ Farben (bis auf Isomorphie)} \\
		\midrule
		\multicolumn{3}{l}{Ecken vom Oktaeder/Seiten vom Würfel} &
		\multicolumn{2}{l}{$(n^6 + 3n^4 + 12n^3 + 8n^2)/24$} \\

		\multicolumn{3}{l}{Ecken vom Würfel/Seiten vom Oktaeder} &
		\multicolumn{2}{l}{$(n^8 + 17n^4 + 6n^2)/24$} \\

		\multicolumn{3}{l}{Kanten vom Würfel/Oktaeder} &
		\multicolumn{2}{l}{$(n^{12} + 6n^7 + 3n^6 + 8n^4 + 6n^3)/24$} \\

		\multicolumn{3}{l}{Ecken/Seiten vom Tetraeder} &
		\multicolumn{2}{l}{$(n^4 + 11n^2)/12$} \\

		\multicolumn{3}{l}{Kanten vom Tetraeder} &
		\multicolumn{2}{l}{$(n^6 + 3n^4 + 8n^2)/12$} \\

		\multicolumn{3}{l}{Ecken vom Ikosaeder/Seiten vom Dodekaeder} &
		\multicolumn{2}{l}{$(n^{12} + 15n^6 + 44n^4)/60$} \\

		\multicolumn{3}{l}{Ecken vom Dodekaeder/Seiten vom Ikosaeder} &
		\multicolumn{2}{l}{$(n^{20} + 15n^{10} + 20n^8 + 24n^4)/60$} \\

		\multicolumn{3}{l}{Kanten vom Dodekaeder/Ikosaeder (evtl. falsch)} &
		\multicolumn{2}{l}{$(n^{30} + 15n^{16} + 20n^{10} + 24n^6)/60$} \\
		\bottomrule
	\end{tabular}
\end{flushleft}

\subsection{Big Integers}
\lstinputlisting{math/bigint.cpp}