From 322480404c722098cc09826c4e6daa8e2c1e9343 Mon Sep 17 00:00:00 2001 From: mzuenni Date: Fri, 6 Sep 2024 21:43:30 +0200 Subject: small latex changes --- content/tcr.tex | 10 +++++++--- 1 file changed, 7 insertions(+), 3 deletions(-) (limited to 'content/tcr.tex') diff --git a/content/tcr.tex b/content/tcr.tex index b327b37..4e4353b 100644 --- a/content/tcr.tex +++ b/content/tcr.tex @@ -1,6 +1,9 @@ - -%maybe size 9pt if too many pages -\documentclass[a4paper,fontsize=7.8pt]{scrartcl} +\documentclass[ + paper=a4, + DIV=calc, + fontsize=7.8pt, + usegeometry +]{scrartcl} % General information. \newcommand{\teamname}{Kindergarten Timelimit} @@ -14,6 +17,7 @@ \usepackage[T1]{fontenc} \usepackage[ngerman]{babel} \usepackage[utf8]{inputenc} +\usepackage[nopatch=footnote]{microtype} \usepackage[hidelinks,pdfencoding=auto]{hyperref} % Include headers. -- cgit v1.2.3 From 9e9c033aa41f786f494cadea43563f83f3e951a3 Mon Sep 17 00:00:00 2001 From: mzuenni Date: Sat, 7 Sep 2024 23:41:49 +0200 Subject: insert divsum --- content/graph/dinicScaling.cpp | 21 +++++++++++++-------- content/graph/graph.tex | 4 ++-- content/math/divSum.cpp | 15 +++++++-------- content/math/gauss.cpp | 12 +++++------- content/math/lgsFp.cpp | 3 +-- content/math/math.tex | 14 ++++++++++---- content/tcr.tex | 1 - tcr.pdf | Bin 673187 -> 691497 bytes 8 files changed, 38 insertions(+), 32 deletions(-) (limited to 'content/tcr.tex') diff --git a/content/graph/dinicScaling.cpp b/content/graph/dinicScaling.cpp index f4e833a..0974b78 100644 --- a/content/graph/dinicScaling.cpp +++ b/content/graph/dinicScaling.cpp @@ -26,17 +26,18 @@ bool bfs(ll lim) { return dist[t] >= 0; } -bool dfs(int v, ll flow) { - if (v == t) return true; +ll dfs(int v, ll flow) { + if (v == t || flow == 0) return flow; for (; pt[v] < sz(adj[v]); pt[v]++) { Edge& e = adj[v][pt[v]]; if (dist[e.to] != dist[v] + 1) continue; - if (e.c - e.f >= flow && dfs(e.to, flow)) { - e.f += flow; - adj[e.to][e.rev].f -= flow; - return true; + ll cur = dfs(e.to, min(e.c - e.f, flow)); + if (cur > 0) { + e.f += cur; + adj[e.to][e.rev].f -= cur; + return cur; }} - return false; + return 0; } ll maxFlow(int source, int target) { @@ -45,7 +46,11 @@ ll maxFlow(int source, int target) { for (ll lim = (1LL << 62); lim >= 1; lim /= 2) { while (bfs(lim)) { pt.assign(sz(adj), 0); - while (dfs(s, lim)) flow += lim; + ll cur; + do { + cur = dfs(s, lim); + flow += cur; + } while (cur > 0); }} return flow; } diff --git a/content/graph/graph.tex b/content/graph/graph.tex index 831f4e5..213c597 100644 --- a/content/graph/graph.tex +++ b/content/graph/graph.tex @@ -211,6 +211,8 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \end{methods} \sourcecode{graph/minCostMaxFlow.cpp} \end{algorithm} +\vfill\null +\columnbreak \subsubsection{Dinic's Algorithm mit Capacity Scaling} \begin{methods} @@ -218,8 +220,6 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \method{addEdge}{fügt eine \textbf{gerichtete} Kante ein}{1} \end{methods} \sourcecode{graph/dinicScaling.cpp} -\vfill\null -\columnbreak \optional{ \subsubsection{Anwendungen} diff --git a/content/math/divSum.cpp b/content/math/divSum.cpp index dc4bc4d..48302b5 100644 --- a/content/math/divSum.cpp +++ b/content/math/divSum.cpp @@ -1,9 +1,8 @@ -// Calculates the sum of (a*i+b)/m for i=0..(n-1) in O(log(n)) -// Note that b should not be negative! ll divSum(ll n, ll m, ll a, ll b){ - if(m == 0) return 0; - ll ans = a/m * n*(n-1) / 2 + b/m * n; - a %= m, b %= m; - ll y = (a*(n-1)+b)/m; - return ans + y*(n-1) - divSum(y, a, m, m-b-1); -} \ No newline at end of file + if (m == 0) return 0; + ll ans = a/m * n*(n-1)/2 + b/m * n; + a %= m; + b %= m; + ll y = (a*(n-1)+b) / m; + return ans + y * (n-1) - divSum(y, a, m, m-b-1); +} diff --git a/content/math/gauss.cpp b/content/math/gauss.cpp index 8129fd2..d431e52 100644 --- a/content/math/gauss.cpp +++ b/content/math/gauss.cpp @@ -14,19 +14,17 @@ void takeAll(int n, int line) { int gauss(int n) { vector done(n, false); for (int i = 0; i < n; i++) { - int swappee = i; // Sucht Pivotzeile für bessere Stabilität. - for (int j = 0; j < n; j++) { - if (done[j]) continue; - if (abs(mat[j][i]) > abs(mat[i][i])) swappee = j; + int j = i; // Sucht Pivotzeile für bessere Stabilität. + for (int k = 0; k < n; k++) { + if (!done[k] && abs(mat[k][i]) > abs(mat[i][i])) j = k; } - swap(mat[i], mat[swappee]); + swap(mat[i], mat[j]); if (abs(mat[i][i]) > EPS) { normalLine(i); takeAll(n, i); done[i] = true; }} - // Ab jetzt nur checks bzgl. Eindeutigkeit/Existenz der Lösung. - for (int i = 0; i < n; i++) { + for (int i = 0; i < n; i++) { // gauss fertig, prüfe Lösung bool allZero = true; for (int j = i; j < n; j++) allZero &= abs(mat[i][j]) <= EPS; if (allZero && abs(mat[i][n]) > EPS) return INCONSISTENT; diff --git a/content/math/lgsFp.cpp b/content/math/lgsFp.cpp index 0241742..bf18c86 100644 --- a/content/math/lgsFp.cpp +++ b/content/math/lgsFp.cpp @@ -22,5 +22,4 @@ void gauss(int n, ll mod) { normalLine(i, mod); takeAll(n, i, mod); done[i] = true; -}} -// für Eindeutigkeit, Existenz etc. siehe LGS über R @\sourceref{math/gauss.cpp}@ +}} // für Eindeutigkeit, Existenz etc. siehe LGS über R @\sourceref{math/gauss.cpp}@ diff --git a/content/math/math.tex b/content/math/math.tex index c15825f..fffdf37 100644 --- a/content/math/math.tex +++ b/content/math/math.tex @@ -306,7 +306,10 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: \method{gauss}{löst LGS}{n^3} \sourcecode{math/gauss.cpp} -\vfill\null\columnbreak +\begin{algorithm}{Inversionszahl} + \vspace{-2pt} + \sourcecode{math/inversions.cpp} +\end{algorithm} \begin{algorithm}{Numerisch Extremstelle bestimmen} \sourcecode{math/goldenSectionSearch.cpp} @@ -316,7 +319,6 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: \sourcecode{math/simpson.cpp} \end{algorithm} - \begin{algorithm}{Polynome, FFT, NTT \& andere Transformationen} Multipliziert Polynome $A$ und $B$. \begin{itemize} @@ -340,8 +342,11 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: \sourcecode{math/transforms/seriesOperations.cpp} \end{algorithm} -\begin{algorithm}{Inversionszahl} - \sourcecode{math/inversions.cpp} + +\begin{algorithm}{Div Sum} + \method{divSum}{berechnet $\sum_{i=0}^{n-1} \frac{a\cdot i + b}{m}$}{\log(n)} + \textbf{Wichtig:} $b$ darf nicht negativ sein! + \sourcecode{math/divSum.cpp} \end{algorithm} \subsection{Satz von \textsc{Sprague-Grundy}} @@ -394,6 +399,7 @@ so gilt \end{methods} \sourcecode{math/binomial0.cpp} Falls $n >= p$ for $\mathit{mod}=p^k$ berechne \textit{fac} und \textit{inv} aber teile $p$ aus $i$ und berechne die häufigkeit von $p$ in $n!$ als $\sum\limits_{i=1}\big\lfloor\frac{n}{p^i}\big\rfloor$ + \columnbreak \begin{methods} \method{calc\_binom}{berechnet Binomialkoeffizient $(n \le 61)$}{k} diff --git a/content/tcr.tex b/content/tcr.tex index 4e4353b..b3cfb17 100644 --- a/content/tcr.tex +++ b/content/tcr.tex @@ -17,7 +17,6 @@ \usepackage[T1]{fontenc} \usepackage[ngerman]{babel} \usepackage[utf8]{inputenc} -\usepackage[nopatch=footnote]{microtype} \usepackage[hidelinks,pdfencoding=auto]{hyperref} % Include headers. diff --git a/tcr.pdf b/tcr.pdf index 488ac70..c16c3cc 100644 Binary files a/tcr.pdf and b/tcr.pdf differ -- cgit v1.2.3 From 45d95c45013bf4ff73570c94c58b7f0212ccdf26 Mon Sep 17 00:00:00 2001 From: mzuenni Date: Sun, 8 Sep 2024 22:16:36 +0200 Subject: moved stuff --- content/math/math.tex | 79 ++++++++++++++++++++++++------------ content/math/minMod.cpp | 26 +++++++----- content/math/tables.tex | 18 -------- content/math/tables/binom.tex | 31 +++++++------- content/math/tables/composite.tex | 45 ++++++++++---------- content/math/tables/nim.tex | 5 ++- content/math/tables/numbers.tex | 59 --------------------------- content/math/tables/platonic.tex | 26 ++++++------ content/math/tables/probability.tex | 17 ++++---- content/math/tables/series.tex | 32 +++++++-------- content/math/tables/stuff.tex | 9 ++-- content/tcr.tex | 3 -- tcr.pdf | Bin 693864 -> 696377 bytes 13 files changed, 148 insertions(+), 202 deletions(-) delete mode 100644 content/math/tables.tex delete mode 100644 content/math/tables/numbers.tex (limited to 'content/tcr.tex') diff --git a/content/math/math.tex b/content/math/math.tex index 6b765ca..c07a41e 100644 --- a/content/math/math.tex +++ b/content/math/math.tex @@ -342,31 +342,6 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: \sourcecode{math/transforms/seriesOperations.cpp} \end{algorithm} - -\begin{algorithm}{Div Sum} - \method{divSum}{berechnet $\sum_{i=0}^{n-1} \left\lfloor \frac{a\cdot i + b}{m} \right\rfloor$}{\log(n)} - \textbf{Wichtig:} $b$ darf nicht negativ sein! - \sourcecode{math/divSum.cpp} -\end{algorithm} - -\begin{algorithm}{Min Mod} - \method{firstVal}{berechnet den ersten Wert von $0,\ a, \ldots,\ a \cdot i \bmod{m}$, der in $[l, r]$ liegt. Gibt $-1$ zurück, falls er nicht existiert.}{\log(m)} - \method{minMod}{berechnet das Minimum von $(a \cdot i + b) \bmod{m}$ für $i \in [0, n)$}{\log(m)} - \textbf{Wichtig:} $0 \leq a, b, l, r < m$ - \sourcecode{math/minMod.cpp} -\end{algorithm} - -\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{Kombinatorik} \paragraph{Wilsons Theorem} @@ -400,13 +375,14 @@ so gilt \paragraph{Binomialkoeffizienten} Die Anzahl der \mbox{$k$-elementigen} Teilmengen einer \mbox{$n$-elementigen} Menge. + \input{math/tables/binom} + \begin{methods} \method{precalc}{berechnet $n!$ und $n!^{-1}$ vor}{\mathit{lim}} \method{calc\_binom}{berechnet Binomialkoeffizient}{1} \end{methods} \sourcecode{math/binomial0.cpp} Falls $n >= p$ for $\mathit{mod}=p^k$ berechne \textit{fac} und \textit{inv} aber teile $p$ aus $i$ und berechne die häufigkeit von $p$ in $n!$ als $\sum\limits_{i=1}\big\lfloor\frac{n}{p^i}\big\rfloor$ - \columnbreak \begin{methods} \method{calc\_binom}{berechnet Binomialkoeffizient $(n \le 61)$}{k} @@ -519,6 +495,54 @@ Die Anzahl der Partitionen von $n$ mit Elementen aus ${1,\dots,k}$. \subsection{The Twelvefold Way \textnormal{(verteile $n$ Bälle auf $k$ Boxen)}} \input{math/tables/twelvefold} +\subsection{Platonische Körper} +\input{math/tables/platonic} + +\input{math/tables/probability} + +\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{Nim-Spiele} +\begin{itemize} + \item[\ding{182}] letzter gewinnt (normal) + \item[\ding{183}] letzter verliert +\end{itemize} +\input{math/tables/nim} + +\subsection{Verschiedenes} +\input{math/tables/stuff} + +\begin{algorithm}{Div Sum} + \method{divSum}{berechnet $\sum_{i=0}^{n-1} \left\lfloor \frac{a\cdot i + b}{m} \right\rfloor$}{\log(n)} + \textbf{Wichtig:} $b$ darf nicht negativ sein! + \sourcecode{math/divSum.cpp} +\end{algorithm} + +\begin{algorithm}{Min Mod} + \begin{methods} + \method{firstVal}{berechnet den ersten Wert von $0,\ a, \ldots,\ a \cdot i \bmod{m}$,}{\log(m)} + \method{}{der in $[l, r]$ liegt. Gibt $-1$ zurück, falls er nicht existiert.}{} + \method{minMod}{berechnet das Minimum von $(a \cdot i + b) \bmod{m}$ für $i \in [0, n)$}{\log(m)} + \end{methods} + \textbf{Wichtig:} $0 \leq a, b, l, r < m$ + \sourcecode{math/minMod.cpp} +\end{algorithm} + +\subsection{Reihen} +\input{math/tables/series} + +\subsection{Wichtige Zahlen} +\input{math/tables/composite} + \optional{ \subsection{Primzahlzählfunktion $\boldsymbol{\pi}$} \begin{methods} @@ -529,7 +553,8 @@ Die Anzahl der Partitionen von $n$ mit Elementen aus ${1,\dots,k}$. \sourcecode{math/piLehmer.cpp} } -%\input{math/tables/numbers} +\subsection{Primzahlzählfunktion $\boldsymbol{\pi}$} +\sourcecode{math/piLegendre.cpp} \begin{algorithm}[optional]{Big Integers} \sourcecode{math/bigint.cpp} diff --git a/content/math/minMod.cpp b/content/math/minMod.cpp index 2db060a..91f31d0 100644 --- a/content/math/minMod.cpp +++ b/content/math/minMod.cpp @@ -1,18 +1,22 @@ -ll firstVal(ll a, ll m, ll l, ll r){ - if(l == 0) return 0; - if(a == 0) return -1; - if((l-1)/a < r/a) return (l+a-1)/a*a; - ll s = (r+a-1)/a*a; - ll v = firstVal(m%a, a, s-r, s-l); +ll firstVal(ll a, ll m, ll l, ll r) { + if (l == 0) return 0; + if (a == 0) return -1; + if ((l-1)/a < r/a) return (l+a-1) / a*a; + ll s = (r+a-1) / a*a; + ll v = firstVal(m % a, a, s-r, s-l); return v == -1 ? -1 : s - v; } -ll minMod(ll n, ll m, ll a, ll b){ - if(a == 0) return b; - ll g = gcd(m, a), c = b%g; - m /= g, a /= g, b /= g; +ll minMod(ll n, ll m, ll a, ll b) { + if (a == 0) return b; + ll g = gcd(m, a); + c = b%g; + m /= g; + a /= g; + b /= g; ll ai = multInv(a, m); - ll l = ai*b % m, r = (n-1 + ai*b) % m; + ll l = ai*b % m; + ll r = (n-1 + ai*b) % m; if(n >= m || l > r) return c; return a * firstVal(ai, m, l, r) % m * g + c; } \ No newline at end of file diff --git a/content/math/tables.tex b/content/math/tables.tex deleted file mode 100644 index 53f3758..0000000 --- a/content/math/tables.tex +++ /dev/null @@ -1,18 +0,0 @@ -\enlargethispage{0.2cm} -\begin{multicols*}{2} - \input{math/tables/binom} - \vfill - \input{math/tables/composite} - \vfill - \input{math/tables/platonic} - \vfill - \input{math/tables/series} - - \columnbreak - - \input{math/tables/probability} - \vfill - \input{math/tables/stuff} - \vfill - \input{math/tables/nim} -\end{multicols*} diff --git a/content/math/tables/binom.tex b/content/math/tables/binom.tex index 878a6b0..9fc9ae3 100644 --- a/content/math/tables/binom.tex +++ b/content/math/tables/binom.tex @@ -1,28 +1,27 @@ -\begin{tabularx}{\linewidth}{|XXXX|} +\begin{expandtable} +\begin{tabularx}{\linewidth}{|C|} \hline - \multicolumn{4}{|c|}{Binomialkoeffizienten} \\ - \hline - \multicolumn{4}{|c|}{ $\frac{n!}{k!(n - k)!} \hfill=\hfill \binom{n}{k} \hfill=\hfill \binom{n}{n - k} \hfill=\hfill \frac{n}{k}\binom{n - 1}{k - 1} \hfill=\hfill \frac{n-k+1}{k}\binom{n}{k - 1} \hfill=\hfill - \binom{n - 1}{k} + \binom{n - 1}{k - 1} \hfill=\hfill + \frac{k+1}{n-k}\binom{n}{k + 1} \hfill=\hfill$\\ + + $\binom{n - 1}{k - 1} + \binom{n - 1}{k} \hfill=\hfill + \binom{n + 1}{k + 1} - \binom{n}{k + 1} \hfill=\hfill (-1)^k \binom{k - n - 1}{k} \hfill\approx\hfill - 2^{n} \cdot \frac{2}{\sqrt{2\pi n}}\cdot\exp\left(-\frac{2(x - \frac{n}{2})^2}{n}\right)$ - } \\ + 2^{n} \cdot \frac{2}{\sqrt{2\pi n}}\cdot\exp\left(-\frac{2(x - \frac{n}{2})^2}{n}\right)$\\ \grayhline - $\sum\limits_{k = 0}^n \binom{n}{k} = 2^n$ & - $\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}$ & - $\sum\limits_{k = 0}^n\binom{r + k}{k} = \binom{r + n + 1}{n}$\\ + $\sum\limits_{k = 0}^n \binom{n}{k} = 2^n\hfill + \sum\limits_{k = 0}^n \binom{k}{m} = \binom{n + 1}{m + 1}\hfill + \sum\limits_{i = 0}^n \binom{n}{i}^2 = \binom{2n}{n}\hfill + \sum\limits_{k = 0}^n\binom{r + k}{k} = \binom{r + n + 1}{n}$\\ - $\binom{n}{m}\binom{m}{k} = \binom{n}{k}\binom{n - k}{m - k}$ & - $\sum\limits_{k = 0}^n \binom{r}{k}\binom{s}{n - k} = \binom{r + s}{n}$ & - \multicolumn{2}{l|}{ - $\sum\limits_{i = 1}^n \binom{n}{i} F_i = F_{2n} \quad F_n = n\text{-th Fib.}$ - }\\ + $\binom{n}{m}\binom{m}{k} = \binom{n}{k}\binom{n - k}{m - k}\hfill + \sum\limits_{k = 0}^n \binom{r}{k}\binom{s}{n - k} = \binom{r + s}{n}\hfill + \sum\limits_{i = 1}^n \binom{n}{i} \mathit{Fib}_i = \mathit{Fib}_{2n}$\\ \hline \end{tabularx} +\end{expandtable} diff --git a/content/math/tables/composite.tex b/content/math/tables/composite.tex index c261db1..7a6ab09 100644 --- a/content/math/tables/composite.tex +++ b/content/math/tables/composite.tex @@ -1,27 +1,26 @@ - -\begin{tabularx}{\linewidth}{|r||r||r|r||r|r|r||C|} +\begin{expandtable} +\begin{tabularx}{\linewidth}{|r||r|R||r||r|} \hline - \multicolumn{8}{|c|}{Important Numbers} \\ + $10^x$ & Highly Composite & \# Divs & \# prime Divs & \# Primes \\ \hline - $10^x$ & Highly Composite & \# Divs & $<$ Prime & $>$ Prime & \# Primes & primorial & \\ - \hline - 1 & 6 & 4 & $-3$ & $+1$ & 4 & 2 & \\ - 2 & 60 & 12 & $-3$ & $+1$ & 25 & 3 & \\ - 3 & 840 & 32 & $-3$ & $+9$ & 168 & 4 & \\ - 4 & 7\,560 & 64 & $-27$ & $+7$ & 1\,229 & 5 & \\ - 5 & 83\,160 & 128 & $-9$ & $+3$ & 9\,592 & 6 & \\ - 6 & 720\,720 & 240 & $-17$ & $+3$ & 78\,498 & 7 & \\ - 7 & 8\,648\,640 & 448 & $-9$ & $+19$ & 664\,579 & 8 & \\ - 8 & 73\,513\,440 & 768 & $-11$ & $+7$ & 5\,761\,455 & 8 & \\ - 9 & 735\,134\,400 & 1\,344 & $-63$ & $+7$ & 50\,847\,534 & 9 & \\ - 10 & 6\,983\,776\,800 & 2\,304 & $-33$ & $+19$ & 455\,052\,511 & 10 & \\ - 11 & 97\,772\,875\,200 & 4\,032 & $-23$ & $+3$ & 4\,118\,054\,813 & 10 & \\ - 12 & 963\,761\,198\,400 & 6\,720 & $-11$ & $+39$ & 37\,607\,912\,018 & 11 & \\ - 13 & 9\,316\,358\,251\,200 & 10\,752 & $-29$ & $+37$ & 346\,065\,536\,839 & 12 & \\ - 14 & 97\,821\,761\,637\,600 & 17\,280 & $-27$ & $+31$ & 3\,204\,941\,750\,802 & 12 & \\ - 15 & 866\,421\,317\,361\,600 & 26\,880 & $-11$ & $+37$ & 29\,844\,570\,422\,669 & 13 & \\ - 16 & 8\,086\,598\,962\,041\,600 & 41\,472 & $-63$ & $+61$ & 279\,238\,341\,033\,925 & 13 & \\ - 17 & 74\,801\,040\,398\,884\,800 & 64\,512 & $-3$ & $+3$ & 2\,623\,557\,157\,654\,233 & 14 & \\ - 18 & 897\,612\,484\,786\,617\,600 & 103\,680 & $-11$ & $+3$ & 24\,739\,954\,287\,740\,860 & 16 & \\ + 1 & 6 & 4 & 2 & 4 \\ + 2 & 60 & 12 & 3 & 25 \\ + 3 & 840 & 32 & 4 & 168 \\ + 4 & 7\,560 & 64 & 5 & 1\,229 \\ + 5 & 83\,160 & 128 & 6 & 9\,592 \\ + 6 & 720\,720 & 240 & 7 & 78\,498 \\ + 7 & 8\,648\,640 & 448 & 8 & 664\,579 \\ + 8 & 73\,513\,440 & 768 & 8 & 5\,761\,455 \\ + 9 & 735\,134\,400 & 1\,344 & 9 & 50\,847\,534 \\ + 10 & 6\,983\,776\,800 & 2\,304 & 10 & 455\,052\,511 \\ + 11 & 97\,772\,875\,200 & 4\,032 & 10 & 4\,118\,054\,813 \\ + 12 & 963\,761\,198\,400 & 6\,720 & 11 & 37\,607\,912\,018 \\ + 13 & 9\,316\,358\,251\,200 & 10\,752 & 12 & 346\,065\,536\,839 \\ + 14 & 97\,821\,761\,637\,600 & 17\,280 & 12 & 3\,204\,941\,750\,802 \\ + 15 & 866\,421\,317\,361\,600 & 26\,880 & 13 & 29\,844\,570\,422\,669 \\ + 16 & 8\,086\,598\,962\,041\,600 & 41\,472 & 13 & 279\,238\,341\,033\,925 \\ + 17 & 74\,801\,040\,398\,884\,800 & 64\,512 & 14 & 2\,623\,557\,157\,654\,233 \\ + 18 & 897\,612\,484\,786\,617\,600 & 103\,680 & 16 & 24\,739\,954\,287\,740\,860 \\ \hline \end{tabularx} +\end{expandtable} diff --git a/content/math/tables/nim.tex b/content/math/tables/nim.tex index 8490d42..66e289e 100644 --- a/content/math/tables/nim.tex +++ b/content/math/tables/nim.tex @@ -1,6 +1,5 @@ +\begin{expandtable} \begin{tabularx}{\linewidth}{|p{0.37\linewidth}|X|} - \hline - \multicolumn{2}{|c|}{Nim-Spiele (\ding{182} letzter gewinnt (normal), \ding{183} letzter verliert)} \\ \hline Beschreibung & Strategie \\ @@ -94,3 +93,5 @@ Periode ab $n = 72$ der Länge $12$.\\ \hline \end{tabularx} +\end{expandtable} + \ No newline at end of file diff --git a/content/math/tables/numbers.tex b/content/math/tables/numbers.tex deleted file mode 100644 index 1dc9f38..0000000 --- a/content/math/tables/numbers.tex +++ /dev/null @@ -1,59 +0,0 @@ -\begin{expandtable} -\begin{tabularx}{\linewidth}{|l|X|} - \hline - \multicolumn{2}{|c|}{Berühmte Zahlen} \\ - \hline - \textsc{Fibonacci} & - $f(0) = 0 \quad - f(1) = 1 \quad - f(n+2) = f(n+1) + f(n)$ \\ - \grayhline - - \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}$ \\ - \grayhline - - \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} $ \\ - \grayhline - - \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}$ \\ - \grayhline - - \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}$ \\ - \grayhline - - \textsc{Stirling} II & - $\stirlingII{n}{1} = \stirlingII{n}{n} = 1 \qquad - \stirlingII{n}{k} = k \stirlingII{n-1}{k} + \stirlingII{n-1}{k-1} = - \frac{1}{k!} \sum\limits_{j=0}^{k} (-1)^{k-j}\binom{k}{j}j^n$\\ - \grayhline - - \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}$\\ - \grayhline - - \textsc{Partitions} & - $p(0,0) = 1 \quad - p(n,k) = 0 \text{ für } k > n \text{ oder } n \leq 0 \text{ oder } k \leq 0$ \\ - & $p(n,k) = p(n-k,k) + p(n-1,k-1)$\\ - \grayhline - - \textsc{Partitions} & - $f(0) = 1 \quad f(n) = 0~(n < 0)$ \\ - & $f(n)=\sum\limits_{k=1}^\infty(-1)^{k-1}f(n - \frac{k(3k+1)}{2})+\sum\limits_{k=1}^\infty(-1)^{k-1}f(n - \frac{k(3k-1)}{2})$\\ - - \hline -\end{tabularx} -\end{expandtable} diff --git a/content/math/tables/platonic.tex b/content/math/tables/platonic.tex index f4ee554..2866ccf 100644 --- a/content/math/tables/platonic.tex +++ b/content/math/tables/platonic.tex @@ -1,39 +1,39 @@ +\begin{expandtable} \begin{tabularx}{\linewidth}{|X|CCCX|} \hline - \multicolumn{5}{|c|}{Platonische Körper} \\ - \hline - Übersicht & Seiten & Ecken & Kanten & dual zu \\ + Übersicht & |F| & |V| & |E| & dual zu \\ \hline Tetraeder & 4 & 4 & 6 & Tetraeder \\ - Würfel/Hexaeder & 6 & 8 & 12 & Oktaeder \\ - Oktaeder & 8 & 6 & 12 & Würfel/Hexaeder\\ + Würfel & 6 & 8 & 12 & Oktaeder \\ + Oktaeder & 8 & 6 & 12 & Würfel\\ Dodekaeder & 12 & 20 & 30 & Ikosaeder \\ Ikosaeder & 20 & 12 & 30 & Dodekaeder \\ \hline \multicolumn{5}{|c|}{Färbungen mit maximal $n$ Farben (bis auf Isomorphie)} \\ \hline - \multicolumn{3}{|l}{Ecken vom Oktaeder/Seiten vom Würfel} & + \multicolumn{3}{|l}{|V| vom Oktaeder/|F| 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{3}{|l}{|V| vom Würfel/|F| vom Oktaeder} & \multicolumn{2}{l|}{$(n^8 + 17n^4 + 6n^2)/24$} \\ - \multicolumn{3}{|l}{Kanten vom Würfel/Oktaeder} & + \multicolumn{3}{|l}{|E| 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{3}{|l}{|V|/|F| vom Tetraeder} & \multicolumn{2}{l|}{$(n^4 + 11n^2)/12$} \\ - \multicolumn{3}{|l}{Kanten vom Tetraeder} & + \multicolumn{3}{|l}{|E| vom Tetraeder} & \multicolumn{2}{l|}{$(n^6 + 3n^4 + 8n^2)/12$} \\ - \multicolumn{3}{|l}{Ecken vom Ikosaeder/Seiten vom Dodekaeder} & + \multicolumn{3}{|l}{|V| vom Ikosaeder/|F| vom Dodekaeder} & \multicolumn{2}{l|}{$(n^{12} + 15n^6 + 44n^4)/60$} \\ - \multicolumn{3}{|l}{Ecken vom Dodekaeder/Seiten vom Ikosaeder} & + \multicolumn{3}{|l}{|V| vom Dodekaeder/|F| vom Ikosaeder} & \multicolumn{2}{l|}{$(n^{20} + 15n^{10} + 20n^8 + 24n^4)/60$} \\ - \multicolumn{3}{|l}{Kanten vom Dodekaeder/Ikosaeder (evtl. falsch)} & + \multicolumn{3}{|l}{|E| vom Dodekaeder/Ikosaeder} & \multicolumn{2}{l|}{$(n^{30} + 15n^{16} + 20n^{10} + 24n^6)/60$} \\ \hline \end{tabularx} +\end{expandtable} diff --git a/content/math/tables/probability.tex b/content/math/tables/probability.tex index f265d10..29f92e1 100644 --- a/content/math/tables/probability.tex +++ b/content/math/tables/probability.tex @@ -1,19 +1,15 @@ -\begin{tabularx}{\linewidth}{|LICIR|} +\begin{expandtable} +\begin{tabularx}{\linewidth}{|LIR|} \hline - \multicolumn{3}{|c|}{ + \multicolumn{2}{|c|}{ Wahrscheinlichkeitstheorie ($A,B$ Ereignisse und $X,Y$ Variablen) } \\ \hline - $\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]}$ & - $A, B$ disj. $\Leftrightarrow \Pr[A \land B] = \Pr[A] \cdot \Pr[B]$ & - $\Pr[A \lor B] = \Pr[A] + \Pr[B] - \Pr[A \land B]$ \\ + $\E(X + Y) = \E(X) + \E(Y)$ & $\Pr[A \vert B] = \frac{\Pr[A \land B]}{\Pr[B]}$ \\ + $\E(\alpha X) = \alpha \E(X)$ & $\Pr[A \lor B] = \Pr[A] + \Pr[B] - \Pr[A \land B]$ \\ + $X, Y$ unabh. $\Leftrightarrow \E(XY) = \E(X) \cdot \E(Y)$ & $A, B$ disj. $\Leftrightarrow \Pr[A \land B] = \Pr[A] \cdot \Pr[B]$\\ \hline \end{tabularx} -\vfill \begin{tabularx}{\linewidth}{|Xlr|lrX|} \hline \multicolumn{6}{|c|}{\textsc{Bertrand}'s Ballot Theorem (Kandidaten $A$ und $B$, $k \in \mathbb{N}$)} \\ @@ -25,3 +21,4 @@ $\#A \geq \#B + k$ & $Num = \frac{a - k + 1 - b}{a - k + 1} \binom{a + b - k}{b}$ & \\ \hline \end{tabularx} +\end{expandtable} diff --git a/content/math/tables/series.tex b/content/math/tables/series.tex index 3042781..9618c2b 100644 --- a/content/math/tables/series.tex +++ b/content/math/tables/series.tex @@ -1,33 +1,33 @@ -\begin{tabularx}{\linewidth}{|XIXIXIX|} - \hline - \multicolumn{4}{|c|}{Reihen} \\ +\begin{expandtable} +\begin{tabularx}{\linewidth}{|XIXIX|} \hline $\sum\limits_{i = 1}^n i = \frac{n(n+1)}{2}$ & $\sum\limits_{i = 1}^n i^2 = \frac{n(n + 1)(2n + 1)}{6}$ & - $\sum\limits_{i = 1}^n i^3 = \frac{n^2 (n + 1)^2}{4}$ & - $H_n = \sum\limits_{i = 1}^n \frac{1}{i}$ \\ + $\sum\limits_{i = 1}^n i^3 = \frac{n^2 (n + 1)^2}{4}$ \\ \grayhline - $\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$ & - $\sum\limits_{i = 0}^\infty ic^i = \frac{c}{(1 - c)^2} \quad \vert c \vert < 1$ \\ + $\sum\limits_{i = 0}^n c^i = \frac{c^{n + 1} - 1}{c - 1} \hfill c \neq 1$ & + $\sum\limits_{i = 0}^\infty c^i = \frac{1}{1 - c} \hfill \vert c \vert < 1$ & + $\sum\limits_{i = 1}^\infty c^i = \frac{c}{1 - c} \hfill \vert c \vert < 1$ \\ \grayhline - + \multicolumn{2}{|lI}{ $\sum\limits_{i = 0}^n ic^i = \frac{nc^{n + 2} - (n + 1)c^{n + 1} + c}{(c - 1)^2} \quad c \neq 1$ } & - \multicolumn{2}{l|}{ + $\sum\limits_{i = 0}^\infty ic^i = \frac{c}{(1 - c)^2} \hfill \vert c \vert < 1$ \\ + \grayhline + + \multicolumn{2}{|lI}{ $\sum\limits_{i = 1}^n iH_i = \frac{n(n + 1)}{2}H_n - \frac{n(n - 1)}{4}$ - } \\ + } & + $H_n = \sum\limits_{i = 1}^n \frac{1}{i}$ \\ \grayhline \multicolumn{2}{|lI}{ - $\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)$ - } \\ + } & + $\sum\limits_{i = 1}^n H_i = (n + 1)H_n - n$ \\ \hline \end{tabularx} +\end{expandtable} diff --git a/content/math/tables/stuff.tex b/content/math/tables/stuff.tex index 3cf8b4c..82f2d3f 100644 --- a/content/math/tables/stuff.tex +++ b/content/math/tables/stuff.tex @@ -1,6 +1,7 @@ -\begin{tabularx}{\linewidth}{|ll|} +\begin{expandtable} +\begin{tabularx}{\linewidth}{|Ll|} \hline - \multicolumn{2}{|C|}{Verschiedenes} \\ + \multicolumn{2}{|c|}{Verschiedenes} \\ \hline Türme von Hanoi, minimale Schirttzahl: & $T_n = 2^n - 1$ \\ @@ -20,7 +21,7 @@ \#Wälder mit $k$ gewurzelten Bäumen & $\frac{k}{n}\binom{n}{k}n^{n-k}$ \\ - \#Wälder mit $k$ gewurzelten Bäumen mit vorgegebenen Wurzelknoten& + \#Wälder mit $k$ gewurzelten~Bäumen mit vorgegebenen Wurzelknoten& $\frac{k}{n}n^{n-k}$ \\ Derangements & @@ -29,4 +30,4 @@ $\lim\limits_{n \to \infty} \frac{!n}{n!} = \frac{1}{e}$ \\ \hline \end{tabularx} - +\end{expandtable} diff --git a/content/tcr.tex b/content/tcr.tex index b3cfb17..6d849d5 100644 --- a/content/tcr.tex +++ b/content/tcr.tex @@ -48,10 +48,7 @@ \input{graph/graph} \input{geometry/geometry} \input{math/math} -\end{multicols*} \clearpage - \input{math/tables} -\begin{multicols*}{3} \input{string/string} \input{python/python} \input{other/other} diff --git a/tcr.pdf b/tcr.pdf index 7dc830e..dbd1055 100644 Binary files a/tcr.pdf and b/tcr.pdf differ -- cgit v1.2.3