\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} Iterativ: \lstinputlisting{math/modPowIterativ.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\equiv~b \mod \ggT(m, n)$. 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{Numerisch Integrieren, Simpsonregel} \lstinputlisting{math/simpson.cpp} \subsection{3D-Kugeln} \lstinputlisting{math/spheres.cpp} \subsection{Longest Increasing Subsequence} \lstinputlisting{math/longestIncreasingSubsequence.cpp} \subsection{Inversionszahl und Mergesort} \lstinputlisting{math/inversions.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*} \lstinputlisting{math/legendre.cpp} \subsection{\textsc{Möbius}-Funktion und \textsc{Möbius}-Inversion} \begin{itemize} \item Seien $f,g : \mathbb{N} \to \mathbb{N}$ und $g(n) := \sum_{d \vert n}f(d)$. Dann ist $f(n) = \sum_{d \vert n}g(d)\mu(\frac{n}{d})$. \item $\sum_{d \vert n}\mu(d) = \begin{cases*} 1 & falls $n = 1$\\ 0 & sonst \end{cases*}$ \end{itemize} \textbf{Beispiel Inklusion/Exklusion:} Gegeben sein eine Sequenz $A={a_1,\ldots,a_n}$ von Zahlen, $1 \leq a_i \leq N$. Zähle die Anzahl der \emph{coprime subsequences}.\newline \textbf{Lösung}: Für jedes $x$, sei $cnt[x]$ die Anzahl der Vielfachen von $x$ in $A$. Es gibt $2^{cnt[x]}-1$ nicht leere Subsequences in $A$, die nur Vielfache von $x$ enthalten. Die Anzahl der Subsequences mit $\ggT=1$ ist gegeben durch $\sum_{i = 1}^N \mu(i) \cdot (2^{cnt[i]} - 1)$. \lstinputlisting{math/mobius.cpp} \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{Partitions} & $f(0,0) = 1 \quad f(n,k) = 0 \text{ für } k > n \text{ oder } n \leq 0 \text{ oder } k \leq 0$ \\ & $f(n,k) = f(n-k,k) + f(n-1,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{1mm} \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} \vspace{1mm} \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{1mm} \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}{p{4.3cm}|p{7cm}} \toprule \multicolumn{2}{c}{Nim-Spiele (\ding{182} letzter gewinnt (normal), \ding{183} letzter verliert)} \\ \midrule Beschreibung & Strategie \\ \midrule $M = [\mathit{pile}_i]$\newline $[x] := \{1, \ldots, x\}$& $\mathit{SG} = \oplus_{i = 1}^n \mathit{pile}_i$\newline \ding{182} Nimm von einem Stapel, sodass $\mathit{SG}$ $0$ wird.\newline \ding{183} Genauso. Außer: Bleiben nur noch Stapel der Größe $1$, erzeuge ungerade Anzahl solcher Stapel.\\ \midrule $M = \{a^m \mid m \geq 0\}$ & $a$ ungerade: $\mathit{SG}_n = n \% 2$\newline $a$ gerade:\newline $\mathit{SG}_n = 2$, falls $n \equiv a \mod (a + 1) $\newline $\mathit{SG}_n = n \% (a + 1) \% 2$, sonst.\\ \midrule $M_{\text{\ding{172}}} = \left[\frac{\mathit{pile}_i}{2}\right]$\newline $M_{\text{\ding{173}}} = \left\{\left\lceil\frac{\mathit{pile}_i}{2}\right\rceil, \mathit{pile}_i\right\}$ & \ding{172} $\mathit{SG}_{2n} = n$, $\mathit{SG}_{2n+1} = \mathit{SG}_n$\newline \ding{173} $\mathit{SG}_0 = 0$, $\mathit{SG}_n = [\log_2 n] + 1$ \\ \midrule $M_{\text{\ding{172}}} = \text{Teiler von $\mathit{pile}_i$}$\newline $M_{\text{\ding{173}}} = \text{echte Teiler von $\mathit{pile}_i$}$ & \ding{172} $\mathit{SG}_0 = 0$, $\mathit{SG}_n = \mathit{SG}_{\text{\ding{173},n}} + 1$\newline \ding{173} $\mathit{ST}_1 = 0$, $\mathit{SG}_n = \text{\#Nullen am Ende von $n_{bin}$}$\\ \midrule $M_{\text{\ding{172}}} = [k]$\newline $M_{\text{\ding{173}}} = S$, ($S$ endlich)\newline $M_{\text{\ding{174}}} = S \cup \{\mathit{pile}_i\}$ & $\mathit{SG}_{\text{\ding{172}}, n} = n \mod (k + 1)$\newline \ding{182} Niederlage bei $\mathit{SG} = 0$\newline \ding{183} Niederlage bei $\mathit{SG} = 1$\newline $\mathit{SG}_{\text{\ding{174}}, n} = \mathit{SG}_{\text{\ding{173}}, n} + 1$\\ \midrule \multicolumn{2}{l}{ Für jedes endliche $M$ ist $\mathit{SG}$ eines Stapels irgendwann periodisch. } \\ \midrule \textsc{Moore}'s Nim:\newline Beliebige Zahl von maximal $k$ Stapeln. & \ding{182} Schreibe $\mathit{pile}_i$ binär. Addiere ohne Übertrag zur Basis $k + 1$. Niederlage, falls Ergebnis gleich 0.\newline \ding{183} Wenn alle Stapel $1$ sind: Niederlage, wenn $n \equiv 1 \mod (k + 1)$. Sonst wie in \ding{182}.\\ \midrule Staircase Nim:\newline $n$ Stapel in einer Reihe. Beliebige Zahl von Stapel $i$ nach Stapel $i-1$. & Niederlage, wenn Nim der ungeraden Spiele verloren ist:\newline $\oplus_{i = 0}^{(n - 1) / 2} \mathit{pile}_{2i + 1} = 0$\\ \midrule \textsc{Lasker}'s Nim:\newline Zwei mögliche Züge:\newline 1) Nehme beliebige Zahl.\newline 2) Teile Stapel in zwei Stapel (ohne Entnahme).& $\mathit{SG}_n = n$, falls $n \equiv 1,2 \mod 4$\newline $\mathit{SG}_n = n + 1$, falls $n \equiv 3 \mod 4$\newline $\mathit{SG}_n = n - 1$, falls $n \equiv 0 \mod 4$\\ \midrule \textsc{Kayles}' Nim:\newline Zwei mögliche Züge:\newline 1) Nehme beliebige Zahl.\newline 2) Teile Stapel in zwei Stapel (mit Entnahme).& Berechne $\mathit{SG}_n$ für kleine $n$ rekursiv.\newline $n \in [72,83]: \quad 4, 1, 2, 8, 1, 4, 7, 2, 1, 8, 2, 7$\newline Periode ab $n = 72$ der Länge $12$.\\ \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$ \\ \#geschlossene 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}$ \\ Derangements & $!n = (n - 1)(!(n - 1) + !(n - 2))$ \\ & $!n = \left\lfloor\frac{n!}{e} + \frac{1}{2}\right\rfloor$ \\ & $\lim\limits_{n \to \infty} \frac{!n}{n!} = \frac{1}{e}$ \\ \bottomrule \end{tabular} % \subsection{Big Integers} % \lstinputlisting{math/bigint.cpp}