From 3a98de95336d3deb5d78cafdde6cc63dc3fd5f4f Mon Sep 17 00:00:00 2001
From: MZuenni <michi.zuendorf@gmail.com>
Date: Mon, 13 Feb 2023 19:39:30 +0100
Subject: squezed in new code :D

---
 math/math.tex | 295 ++++++++++++++++++++++++++++++----------------------------
 1 file changed, 152 insertions(+), 143 deletions(-)

(limited to 'math/math.tex')

diff --git a/math/math.tex b/math/math.tex
index feb0466..31fbdd6 100644
--- a/math/math.tex
+++ b/math/math.tex
@@ -1,38 +1,26 @@
 \section{Mathe}
 
-\begin{algorithm}{Zykel Erkennung}
-	\begin{methods}
-		\method{cycleDetection}{findet Zyklus von $x_0$ und länge in $f$}{b+l}
-	\end{methods}
-	\sourcecode{math/cycleDetection.cpp}
-\end{algorithm}
-
-\begin{algorithm}{Permutationen}
-	\begin{methods}
-		\method{kthperm}{findet $k$-te Permutation \big($k \in [0, n!$)\big)}{n\*\log(n)}
-	\end{methods}
-	\sourcecode{math/kthperm.cpp}
-	\begin{methods}
-		\method{permIndex}{bestimmt index der Permutation \big($\mathit{res} \in [0, n!$)\big)}{n\*\log(n)}
-	\end{methods}
-	\sourcecode{math/permIndex.cpp}
+\begin{algorithm}{Longest Increasing Subsequence}
+	\begin{itemize}
+		\item \code{lower\_bound} $\Rightarrow$ streng monoton
+		\item \code{upper\_bound} $\Rightarrow$ monoton
+	\end{itemize}
+	\sourcecode{math/longestIncreasingSubsequence.cpp}
 \end{algorithm}
 
-\paragraph{Lemma von \textsc{Bézout}}
-Sei $(x, y)$ eine Lösung der diophantischen Gleichung $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{\textsc{Pell}-Gleichungen}
-Sei $(\overline{x}, \overline{y})$ die Lösung von $x^2 - ny^2 = 1$, die $x>1$ minimiert.
-Sei $(\tilde{x}, \tilde{y})$ die Lösung von $x^2-ny^2 = c$, die $x>1$ minimiert. Dann lassen
-sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
-\begin{align*}
-	x_1&\coloneqq \tilde{x}, & y_1&\coloneqq\tilde{y}\\
-	x_{k+1}&\coloneqq \overline{x}x_k+n\overline{y}y_k, & y_{k+1}&\coloneqq\overline{x}y_k+\overline{y}x_k
-\end{align*}
+\subsection{Mod-Exponent und Multiplikation über $\boldsymbol{\mathbb{F}_p}$}
+%\vspace{-1.25em}
+%\begin{multicols}{2}
+\method{mulMod}{berechnet $a \cdot b \bmod n$}{\log(b)}
+\sourcecode{math/modMulIterativ.cpp}
+%	\vfill\null\columnbreak
+\method{powMod}{berechnet $a^b \bmod n$}{\log(b)}
+\sourcecode{math/modPowIterativ.cpp}
+%\end{multicols}
+%\vspace{-2.75em}
+\begin{itemize}
+	\item für $a > 10^9$ \code{__int128} oder \code{modMul} benutzten! 
+\end{itemize}
 
 \begin{algorithm}{ggT, kgV, erweiterter euklidischer Algorithmus}
 	\runtime{\log(a) + \log(b)}
@@ -49,7 +37,7 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 	$\alpha n + \beta p = 1$.
 	\item Nach Kongruenz gilt $\alpha n + \beta p \equiv \alpha n \equiv 1 \bmod p$.
 	\item $n^{-1} :\equiv \alpha \bmod p$
-	\end{itemize}
+\end{itemize}
 \textbf{Sonst $\boldsymbol{\ggT(n, p) > 1}$:}\quad Es existiert kein $x^{-1}$.
 \sourcecode{math/multInv.cpp}
 
@@ -62,38 +50,55 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 	\sourcecode{math/linearCongruence.cpp}
 \end{algorithm}
 
-\subsection{Mod-Exponent und Multiplikation über $\boldsymbol{\mathbb{F}_p}$}
-%\vspace{-1.25em}
-%\begin{multicols}{2}
-	\method{mulMod}{berechnet $a \cdot b \bmod n$}{\log(b)}
-	\sourcecode{math/modMulIterativ.cpp}
-%	\vfill\null\columnbreak
-	\method{powMod}{berechnet $a^b \bmod n$}{\log(b)}
-	\sourcecode{math/modPowIterativ.cpp}
-%\end{multicols}
-%\vspace{-2.75em}
-\begin{itemize}
-	\item für $a > 10^9$ \code{__int128} oder \code{modMul} benutzten! 
-\end{itemize}
+\paragraph{Lemma von \textsc{Bézout}}
+Sei $(x, y)$ eine Lösung der diophantischen Gleichung $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)
+\]
 
-\begin{algorithm}{Matrix-Exponent}
+\paragraph{\textsc{Pell}-Gleichungen}
+Sei $(\overline{x}, \overline{y})$ die Lösung von $x^2 - ny^2 = 1$, die $x>1$ minimiert.
+Sei $(\tilde{x}, \tilde{y})$ die Lösung von $x^2-ny^2 = c$, die $x>1$ minimiert. Dann lassen
+sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
+\begin{align*}
+	x_1&\coloneqq \tilde{x}, & y_1&\coloneqq\tilde{y}\\
+	x_{k+1}&\coloneqq \overline{x}x_k+n\overline{y}y_k, & y_{k+1}&\coloneqq\overline{x}y_k+\overline{y}x_k
+\end{align*}
+
+
+\begin{algorithm}{Zykel Erkennung}
 	\begin{methods}
-		\method{precalc}{berechnet $m^{2^b}$ vor}{\log(b)\*n^3}
-		\method{calc}{berechnet $m^b_{y,x}$}{\log(b)\cdot n^2}
+		\method{cycleDetection}{findet Zyklus von $x_0$ und Länge in $f$}{b+l}
 	\end{methods}
-	\sourcecode{math/matrixPower.cpp}
+	\sourcecode{math/cycleDetection.cpp}
 \end{algorithm}
 
-\begin{algorithm}{Berlekamp-Massey}
+\begin{algorithm}{Permutationen}
 	\begin{methods}
-		\method{BerlekampMassey}{Berechnet ein lineare Recurenz $n$-ter Ordnung}{n^2}
-		\method{}{aus den ersten $2n$ Werte}{}
+		\method{kthperm}{findet $k$-te Permutation \big($k \in [0, n!$)\big)}{n\*\log(n)}
 	\end{methods}
-	\sourcecode{math/berlekampMassey.cpp}
+	\sourcecode{math/kthperm.cpp}
+	\begin{methods}
+		\method{permIndex}{bestimmt Index der Permutation \big($\mathit{res} \in [0, n!$)\big)}{n\*\log(n)}
+	\end{methods}
+	\sourcecode{math/permIndex.cpp}
 \end{algorithm}
 
 \begin{algorithm}{Lineare-Recurenz}
-	Sei $f(n)=c_{n-1}f(n-1)+c_{n-2}f(n-2)+\dots + c_0f(0)$ eine Lineare Recurenz. Dann kann das \mbox{$k$-te} folgenglid in \runtime{n^3\log(k)} brechnet werden.
+	\begin{methods}
+		\method{BerlekampMassey}{Berechnet eine lineare Recurenz $n$-ter Ordnung}{n^2}
+		\method{}{aus den ersten $2n$ Werte}{}
+	\end{methods}
+	\sourcecode{math/berlekampMassey.cpp}
+	Sei $f(n)=c_{n-1}f(n-1)+c_{n-2}f(n-2)+\dots + c_0f(0)$ eine lineare Recurenz.
+	
+	\begin{methods}
+		\method{kthTerm}{Berechnet $k$-ten Term einer Recurenz $n$-ter Ordnung}{\log(k)\cdot n^2}
+	\end{methods}
+	\sourcecode{math/linearRecurence.cpp}
+	Alternativ kann der \mbox{$k$-te} Term in \runtime{n^3\log(k)} berechnet werden:
+	\small
 	$$\renewcommand\arraystretch{1.5}
 	\setlength\arraycolsep{3pt}
 	\begin{pmatrix} 
@@ -113,15 +118,24 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 	\end{pmatrix}
 	~~=~~
 	\begin{pmatrix} 
-	f(n-1+k) \\
-	f(n-2+k) \\
-	\smash{\vdots} \\
-	\smash{\vdots} \\
-	f(k) \makebox[0pt][l]{\hspace{15pt}$\vcenter{\hbox{\huge$\leftarrow$}}$}\\
+		f(n-1+k) \\
+		f(n-2+k) \\
+		\smash{\vdots} \\
+		\smash{\vdots} \\
+		f(k) \makebox[0pt][l]{\hspace{15pt}$\vcenter{\hbox{\huge$\leftarrow$}}$}\\
 	\end{pmatrix}
 	$$
 \end{algorithm}
 
+
+\begin{algorithm}{Matrix-Exponent}
+	\begin{methods}
+		\method{precalc}{berechnet $m^{2^b}$ vor}{\log(b)\*n^3}
+		\method{calc}{berechnet $m^b_{y,x}$}{\log(b)\cdot n^2}
+	\end{methods}
+	\sourcecode{math/matrixPower.cpp}
+\end{algorithm}
+
 \begin{algorithm}{Chinesischer Restsatz}
 	\begin{itemize}
 		\item Extrem anfällig gegen Overflows. Evtl. häufig 128-Bit Integer verwenden.
@@ -140,33 +154,42 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 	\sourcecode{math/chineseRemainder.cpp}
 \end{algorithm}
 
-\begin{algorithm}{Primzahltest \& Faktorisierung}
-	\method{isPrime}{prüft ob Zahl prim ist}{\log(n)^2}
-	\sourcecode{math/millerRabin.cpp}
-	\method{rho}{findet zufälligen Teiler}{\sqrt[\leftroot{3}\uproot{2}3]{n}}
-	\sourcecode{math/rho.cpp}
-	%\method{squfof}{findet zufälligen Teiler}{\sqrt[\leftroot{4}\uproot{2}4]{n}}
-	%\sourcecode{math/squfof.cpp}
+\begin{algorithm}{Teiler}
+	\begin{methods}
+		\method{countDivisors}{Zählt Teiler von $n$}{n^\frac{1}{3}}
+		\method{isPrime}{prüft ob Zahl prim ist}{1}
+	\end{methods}
+	\sourcecode{math/divisors.cpp}
 \end{algorithm}
 
-\begin{algorithm}{Primzahlsieb von \textsc{Eratosthenes}}
+\begin{algorithm}{Primitivwurzeln}
 	\begin{itemize}
-		\item Kann erweitert werden: Für jede Zahl den \{kleinsten, größten\} Primfaktor speichern, Liste von Primzahlen berechnen
-		\item Bis $10^8$ in unter 64MB Speicher (lange Berechnung)
+		\item Primitivwurzel modulo $n$ existiert $\Leftrightarrow$ $n \in \{2,\ 4,\ p^\alpha,\ 2\cdot p^\alpha \mid\ 2 < p \in \mathbb{P},\ \alpha \in \mathbb{N}\}$
+		\item es existiert entweder keine oder $\varphi(\varphi(n))$ inkongruente Primitivwurzeln
+		\item Sei $g$ Primitivwurzel modulo $n$.
+		Dann gilt:\newline
+		Das kleinste $k$, sodass $g^k \equiv 1 \bmod n$, ist $k = \varphi(n)$.
 	\end{itemize}
 	\begin{methods}
-		\method{primeSieve}{berechnet Primzahlen und Anzahl}{n\*\log(\log(n))}
-		\method{isPrime}{prüft ob Zahl prim ist}{1}
+		\method{isPrimitive}{prüft ob $g$ eine Primitivwurzel ist}{\log(\varphi(n))\*\log(n)}
+		\method{findPrimitive}{findet Primitivwurzel (oder -1)}{\abs{ans}\*\log(\varphi(n))\*\log(n)}
 	\end{methods}
-	\sourcecode{math/primeSieve.cpp}
+	\sourcecode{math/primitiveRoot.cpp}
 \end{algorithm}
 
-\begin{algorithm}{Teiler}
+\begin{algorithm}{Diskreter Logarithmus}
 	\begin{methods}
-		\method{countDivisors}{Zählt teiler von $n$}{n^\frac{1}{3}}
-		\method{isPrime}{prüft ob Zahl prim ist}{1}
+		\method{solve}{bestimmt Lösung $x$ für $a^x=b \bmod m$}{\sqrt{m}\*\log(m)}
 	\end{methods}
-	\sourcecode{math/divisors.cpp}
+	\sourcecode{math/discreteLogarithm.cpp}
+\end{algorithm}
+%TODO
+\begin{algorithm}{Diskrete \textrm{\textit{n}}-te Wurzel}
+	\begin{methods}
+		\method{root}{bestimmt Lösung $x$ für $x^a=b \bmod m$ }{\sqrt{m}\*\log(m)}
+	\end{methods}
+	Alle Lösungen haben die Form $g^{c + \frac{i \cdot \phi(n)}{\gcd(a, \phi(n))}}$
+	\sourcecode{math/discreteNthRoot.cpp}
 \end{algorithm}
 
 \subsection{Primzahlzählfunktion $\boldsymbol{\pi}$}
@@ -176,23 +199,36 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 	\method{pi}{zählt Primzahlen  $\leq n$ ($n < N^2$)}{n^{2/3}}
 \end{methods}
 \sourcecode{math/piLehmer.cpp}
+\clearpage
 
-\subsection{\textsc{Euler}sche $\boldsymbol{\varphi}$-Funktion}
-\begin{itemize}
-	\item Zählt die relativ primen Zahlen $\leq n$.
+\subsection{LGS über $\boldsymbol{\mathbb{F}_p}$}
+\method{gauss}{löst LGS}{n^3}
+\sourcecode{math/lgsFp.cpp}
 
-	\item Multiplikativ:
-	$\gcd(a,b) = 1 \Longrightarrow \varphi(a) \cdot \varphi(b) = \varphi(ab)$
+\subsection{LGS über $\boldsymbol{\mathbb{R}}$}
+\sourcecode{math/gauss.cpp}
 
-	\item $p$ prim, $k \in \mathbb{N}$:
-	$~\varphi(p^k) = p^k - p^{k - 1}$
 
-	\item \textbf{\textsc{Euler}'s Theorem:}
-		Für $b \geq \varphi(c)$ gilt: $a^b \equiv a^{b \bmod \varphi(c) + \varphi(c)} \pmod{c}$. Darüber hinaus gilt: $\gcd(a, c) = 1 \Leftrightarrow a^b \equiv a^{b \bmod \varphi(c)} \pmod{c}$.
-	Falls $m$ prim ist, liefert das den \textbf{kleinen Satz von \textsc{Fermat}}:
-	$a^{m} \equiv a \pmod{m}$
-\end{itemize}
-\sourcecode{math/phi.cpp}
+\begin{algorithm}{Primzahltest \& Faktorisierung}
+	\method{isPrime}{prüft ob Zahl prim ist}{\log(n)^2}
+	\sourcecode{math/millerRabin.cpp}
+	\method{rho}{findet zufälligen Teiler}{\sqrt[\leftroot{3}\uproot{2}4]{n}}
+	\sourcecode{math/rho.cpp}
+	%\method{squfof}{findet zufälligen Teiler}{\sqrt[\leftroot{4}\uproot{2}4]{n}}
+	%\sourcecode{math/squfof.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Primzahlsieb von \textsc{Eratosthenes}}
+	\begin{itemize}
+		\item Kann erweitert werden: Für jede Zahl den \{kleinsten, größten\} Primfaktor speichern, Liste von Primzahlen berechnen
+		\item Bis $10^8$ in unter 64MB Speicher (lange Berechnung)
+	\end{itemize}
+	\begin{methods}
+		\method{primeSieve}{berechnet Primzahlen und Anzahl}{n\*\log(\log(n))}
+		\method{isPrime}{prüft ob Zahl prim ist}{1}
+	\end{methods}
+	\sourcecode{math/primeSieve.cpp}
+\end{algorithm}
 
 \begin{algorithm}{\textsc{Möbius}-Funktion und \textsc{Möbius}-Inversion}
 	\begin{itemize}
@@ -200,8 +236,8 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 		Dann ist $f(n) = \sum_{d \vert n}g(d)\mu(\frac{n}{d})$.
 		\item $\sum\limits_{d \vert n}\mu(d) =
 		\begin{cases*}
-		1 & falls $n = 1$\\
-		0 & sonst
+			1 & falls $n = 1$\\
+			0 & sonst
 		\end{cases*}$
 	\end{itemize}
 	\textbf{Beispiel Inklusion/Exklusion:}
@@ -212,43 +248,24 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 	Die Anzahl der Subsequences mit $\ggT=1$ ist gegeben durch $\sum_{i = 1}^N \mu(i) \cdot (2^{cnt[i]} - 1)$.
 	\sourcecode{math/mobius.cpp}
 \end{algorithm}
+\clearpage
 
-\begin{algorithm}{Primitivwurzeln}
-	\begin{itemize}
-		\item Primitivwurzel modulo $n$ existiert $\Leftrightarrow$ $n \in \{2,\ 4,\ p^\alpha,\ 2\cdot p^\alpha \mid\ 2 < p \in \mathbb{P},\ \alpha \in \mathbb{N}\}$
-		\item es existiert entweder keine oder $\varphi(\varphi(n))$ inkongruente Primitivwurzeln
-		\item Sei $g$ Primitivwurzel modulo $n$.
-		Dann gilt:\newline
-		Das kleinste $k$, sodass $g^k \equiv 1 \bmod n$, ist $k = \varphi(n)$.
-	\end{itemize}
-	\begin{methods}
-		\method{isPrimitive}{prüft ob $g$ eine Primitivwurzel ist}{\log(\varphi(n))\*\log(n)}
-		\method{findPrimitive}{findet Primitivwurzel (oder -1)}{\abs{ans}\*\log(\varphi(n))\*\log(n)}
-	\end{methods}
-	\sourcecode{math/primitiveRoot.cpp}
-\end{algorithm}
+\subsection{\textsc{Euler}sche $\boldsymbol{\varphi}$-Funktion}
+\begin{itemize}
+	\item Zählt die relativ primen Zahlen $\leq n$.
 
-\begin{algorithm}{Diskreter Logarithmus}
-	\begin{methods}
-		\method{solve}{bestimmt Lösung $x$ für $a^x=b \bmod m$}{\sqrt{m}\*\log(m)}
-	\end{methods}
-	\sourcecode{math/discreteLogarithm.cpp}
-\end{algorithm}
-%TODO
-\begin{algorithm}{Diskrete \textrm{\textit{n}}-te Wurzel}
-	\begin{methods}
-		\method{root}{bestimmt Lösung $x$ für $x^a=b \bmod m$ }{\sqrt{m}\*\log(m)}
-	\end{methods}
-	Alle Lösungen haben die Form $g^{c + \frac{i \cdot \phi(n)}{\gcd(a, \phi(n))}}$
-	\sourcecode{math/discreteNthRoot.cpp}
-\end{algorithm}
+	\item Multiplikativ:
+	$\gcd(a,b) = 1 \Longrightarrow \varphi(a) \cdot \varphi(b) = \varphi(ab)$
 
-\subsection{LGS über $\boldsymbol{\mathbb{F}_p}$}
-\method{gauss}{löst LGS}{n^3}
-\sourcecode{math/lgsFp.cpp}
+	\item $p$ prim, $k \in \mathbb{N}$:
+	$~\varphi(p^k) = p^k - p^{k - 1}$
 
-\subsection{LGS über $\boldsymbol{\mathbb{R}}$}
-\sourcecode{math/gauss.cpp}
+	\item \textbf{\textsc{Euler}'s Theorem:}
+		Für $b \geq \varphi(c)$ gilt: $a^b \equiv a^{b \bmod \varphi(c) + \varphi(c)} \pmod{c}$. Darüber hinaus gilt: $\gcd(a, c) = 1 \Leftrightarrow a^b \equiv a^{b \bmod \varphi(c)} \pmod{c}$.
+	Falls $m$ prim ist, liefert das den \textbf{kleinen Satz von \textsc{Fermat}}:
+	$a^{m} \equiv a \pmod{m}$
+\end{itemize}
+\sourcecode{math/phi.cpp}
 
 \begin{algorithm}{Polynome, FFT, NTT \& andere Transformationen}
 	Multipliziert Polynome $A$ und $B$.
@@ -257,8 +274,8 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 		\item Vektoren \lstinline{a} und \lstinline{b} müssen mindestens Größe
 		$\deg(A \cdot B) + 1$ haben.
 		Größe muss eine Zweierpotenz sein.
-		\item Für ganzzahlige Koeffizienten: \lstinline{(int)round(real(a[i]))}
-		\item xor, or und and Transform funktioniert auch mit \code{double} oder modulo einer Primzahl $p$ falls $p \geq 2^{\texttt{bits}}$
+		\item Für ganzzahlige Koeffizienten: \lstinline{(ll)round(real(a[i]))}
+		\item \emph{xor}, \emph{or} und \emph{and} Transform funktioniert auch mit \code{double} oder modulo einer Primzahl $p$ falls $p \geq 2^{\texttt{bits}}$
 	\end{itemize}
 	%\lstinputlisting{math/fft.cpp}
 	%\lstinputlisting{math/ntt.cpp}
@@ -278,14 +295,6 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 	\sourcecode{math/simpson.cpp}
 \end{algorithm}
 
-\begin{algorithm}{Longest Increasing Subsequence}
-	\begin{itemize}
-		\item \code{lower\_bound} $\Rightarrow$ streng monoton
-		\item \code{upper\_bound} $\Rightarrow$ monoton
-	\end{itemize}
-	\sourcecode{math/longestIncreasingSubsequence.cpp}
-\end{algorithm}
-
 \begin{algorithm}{\textsc{Legendre}-Symbol}
 	Sei $p \geq 3$ eine Primzahl, $a \in \mathbb{Z}$:
 	\begin{align*}
@@ -375,27 +384,27 @@ so gilt
 \[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{4n - 2}{n+1} \cdot C_{n-1}\]
 \begin{itemize}
-	\item Formel $1$ erlaubt berechnung ohne Division in \runtime{n^2}
-	\item Formel $2$ und $3$ erlauben berechnung in \runtime{n}
+	\item Formel $1$ erlaubt Berechnung ohne Division in \runtime{n^2}
+	\item Formel $2$ und $3$ erlauben Berechnung in \runtime{n}
 \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.
+Dabei wird entweder ein Anstieg in zwei gesplitted oder ein Anstieg um $n$ ergänzt.
 \[\eulerI{n}{0} = \eulerI{n}{n-1} = 1 \quad
 \eulerI{n}{k} = (k+1) \eulerI{n-1}{k} + (n-k) \eulerI{n-1}{k-1}=
 \sum_{i=0}^{k} (-1)^i\binom{n+1}{i}(k+1-i)^n\]
 \begin{itemize}
-	\item Formel $1$ erlaubt berechnung ohne Division in \runtime{n^2}
-	\item Formel $2$ erlaubt berechnung in \runtime{n\log(n)}
+	\item Formel $1$ erlaubt Berechnung ohne Division in \runtime{n^2}
+	\item Formel $2$ erlaubt Berechnung in \runtime{n\log(n)}
 \end{itemize}
 
 \paragraph{\textsc{Euler}-Zahlen 2. Ordnung}
 Die Anzahl der Permutationen von $\{1,1, \ldots, n,n\}$ mit genau $k$ Anstiegen.
 \[\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}\]
 \begin{itemize}
-	\item Formel erlaubt berechnung ohne Division in \runtime{n^2}
+	\item Formel erlaubt Berechnung ohne Division in \runtime{n^2}
 \end{itemize}
 
 \paragraph{\textsc{Stirling}-Zahlen 1. Ordnung}
@@ -416,13 +425,13 @@ Dazu kommt der Fall, dass die $n$ in ihrer eigenen Teilmenge (alleine) steht.
 \stirlingII{n}{k} = k \stirlingII{n-1}{k} + \stirlingII{n-1}{k-1} =
 \frac{1}{k!} \sum\limits_{i=0}^{k} (-1)^{k-i}\binom{k}{i}i^n\]
 \begin{itemize}
-	\item Formel $1$ erlaubt berechnung ohne Division in \runtime{n^2}
-	\item Formel $2$ erlaubt berechnung in \runtime{n\log(n)}
+	\item Formel $1$ erlaubt Berechnung ohne Division in \runtime{n^2}
+	\item Formel $2$ erlaubt Berechnung in \runtime{n\log(n)}
 \end{itemize}
 
 \paragraph{\textsc{Bell}-Zahlen}
 Anzahl der Partitionen von $\{1, \ldots, n\}$.
-Wie \textsc{Striling}-Zahlen 2. Ordnung ohne Limit durch $k$.
+Wie \textsc{Stirling}-Zahlen 2. Ordnung ohne Limit durch $k$.
 \[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}\qquad\qquad B_{p^m+n}\equiv m\cdot B_n + B_{n+1} \bmod{p}\]
-- 
cgit v1.2.3

