From ddd6805b49d7b4d6e36445ffac00bef55dbc9c86 Mon Sep 17 00:00:00 2001
From: mzuenni <michi.zuendorf@gmail.com>
Date: Fri, 15 Aug 2025 17:29:23 +0200
Subject: fix typos

---
 content/math/math.tex | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

(limited to 'content/math/math.tex')

diff --git a/content/math/math.tex b/content/math/math.tex
index 4ac6c9e..993af13 100644
--- a/content/math/math.tex
+++ b/content/math/math.tex
@@ -451,7 +451,7 @@ Die Anzahl der Permutationen von $\{1,1, \ldots, n,n\}$ mit genau $k$ Anstiegen.
 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.
 \[\stirlingI{0}{0} = 1 \qquad
-\stirlingI{n}{0} = \stirlingI{0}{n} = 0 \qquad
+\stirlingI{n}{0} = \stirlingI{0}{k} = 0 \qquad
 \stirlingI{n}{k} = \stirlingI{n-1}{k-1} + (n-1) \stirlingI{n-1}{k}\]
 \begin{itemize}
 	\item Formel erlaubt berechnung ohne Division in \runtime{n^2}
@@ -476,7 +476,7 @@ 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{Stirling}-Zahlen 2. Ordnung ohne Limit durch $k$.
-\[B_1 = 1 \qquad
+\[B_0 = 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


From 606f638f580d815503ee685f75ee4ab22a71fe60 Mon Sep 17 00:00:00 2001
From: mzuenni <michi.zuendorf@gmail.com>
Date: Sat, 16 Aug 2025 15:47:01 +0200
Subject: added mini oeis

---
 content/math/math.tex |  33 ++++++++++++++++++++++++---------
 tcr.pdf               | Bin 698759 -> 700080 bytes
 2 files changed, 24 insertions(+), 9 deletions(-)

(limited to 'content/math/math.tex')

diff --git a/content/math/math.tex b/content/math/math.tex
index 993af13..cb352f4 100644
--- a/content/math/math.tex
+++ b/content/math/math.tex
@@ -402,7 +402,8 @@ so gilt
 %	\sourcecode{math/binomial2.cpp}
 %\end{algorithm}
 
-\paragraph{\textsc{Catalan}-Zahlen}
+\paragraph{\textsc{Catalan}-Zahlen:}
+$1,~1,~2,~5,~14,~42,~132,~429,~1430,~4862,~16796,~58786,~208012,~742900$
 \begin{itemize}
 	\item Die \textsc{Catalan}-Zahl $C_n$ gibt an:
 	\begin{itemize}
@@ -423,12 +424,14 @@ so gilt
 
 \paragraph{\textsc{Catalan}-Convolution}
 \begin{itemize}
-	\item Anzahl an Klammerausdrücken mit $n+k$ Klammerpaaren, die mit $(^k$ beginnen.
+	\item Anzahl an Klammerausdrücken mit $n+k$ Klammerpaaren, die mit $\texttt{(}^k$ beginnen.
 \end{itemize}
 \[C^k_0 = 1\qquad C^k_n = \sum\limits_{\mathclap{a_0+a_1+\dots+a_k=n}} C_{a_0}C_{a_1}\cdots C_{a_k} =
 \frac{k+1}{n+k+1}\binom{2n+k}{n} = \frac{(2n+k-1)\cdot(2n+k)}{n(n+k+1)} \cdot C_{n-1}\]
 
-\paragraph{\textsc{Euler}-Zahlen 1. Ordnung}
+\paragraph{\textsc{Euler}-Zahlen 1. Ordnung:}
+$|~1~|~1~|~1,~1~|~1,~4,~1~|~1,~11,~11,~1~|~1,~26,~66,~26,~1~|$
+
 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 Anstieg in zwei gesplitted oder ein Anstieg um $n$ ergänzt.
@@ -440,14 +443,18 @@ Dabei wird entweder ein Anstieg in zwei gesplitted oder ein Anstieg um $n$ ergä
 	\item Formel $2$ erlaubt Berechnung in \runtime{n\log(n)}
 \end{itemize}
 
-\paragraph{\textsc{Euler}-Zahlen 2. Ordnung}
+\paragraph{\textsc{Euler}-Zahlen 2. Ordnung:}
+$|~1~|~1,~0~|~1,~2,~0~|~1,~8,~6,~0~|~1,~22,~58,~24,~0~|$
+
 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}
 \end{itemize}
 
-\paragraph{\textsc{Stirling}-Zahlen 1. Ordnung}
+\paragraph{\textsc{Stirling}-Zahlen 1. Ordnung:}
+$|~1~|~0,~1~|~0,~1,~1~|~0,~2,~3,~1~|~0,~6,~11,~6,~1~|$
+
 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.
 \[\stirlingI{0}{0} = 1 \qquad
@@ -458,14 +465,17 @@ Es gibt zwei Möglichkeiten für die $n$-te Zahl. Entweder sie bildet einen eige
 \end{itemize}
 \[\sum_{k=0}^{n}\pm\stirlingI{n}{k}x^k=x(x-1)(x-2)\cdots(x-n+1)\]
 \begin{itemize}
-	\item Berechne Polynom mit FFT und benutzte betrag der Koeffizienten \runtime{n\log(n)^2} (nur ungefähr gleich große Polynome zusammen multiplizieren beginnend mit $x-k$)
+	\item Berechne Polynom mit FFT und benutzte betrag der Koeffizienten \runtime{n\log(n)^2} (nur ca. gleich große Polynome zusammen multiplizieren beginnend mit $x-k$)
 \end{itemize}
 
-\paragraph{\textsc{Stirling}-Zahlen 2. Ordnung}
+\paragraph{\textsc{Stirling}-Zahlen 2. Ordnung:}
+$|~1~|~0,~1~|~0,~1,~1~|~0,~1,~3,~1~|~0,~1,~7,~6,~1~|$
+
 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.
 \[\stirlingII{n}{1} = \stirlingII{n}{n} = 1 \qquad
+\stirlingII{n}{0} = 0 \qquad
 \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}
@@ -473,14 +483,18 @@ Dazu kommt der Fall, dass die $n$ in ihrer eigenen Teilmenge (alleine) steht.
 	\item Formel $2$ erlaubt Berechnung in \runtime{n\log(n)}
 \end{itemize}
 
-\paragraph{\textsc{Bell}-Zahlen}
+\paragraph{\textsc{Bell}-Zahlen:}
+$1,~1,~2,~5,~15,~52,~203,~877,~4140,~21147,~115975,~678570,~4213597$
+
 Anzahl der Partitionen von $\{1, \ldots, n\}$.
 Wie \textsc{Stirling}-Zahlen 2. Ordnung ohne Limit durch $k$.
 \[B_0 = 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}\]
 
-\paragraph{Partitions}
+\paragraph{Partitions:}
+$|~1~|~0,~1~|~0,~1,~1~|~0,~1,~1,~1~|~0,~1,~2,~1,~1~|~0,~1,~2,~2,~1,~1~|~0,~1,~3,~3,~2,~1,~1~|$
+
 Die Anzahl der Partitionen von $n$ in genau $k$ positive Summanden.
 Die Anzahl der Partitionen von $n$ mit Elementen aus ${1,\dots,k}$.
 \begin{align*}
@@ -489,6 +503,7 @@ Die Anzahl der Partitionen von $n$ mit Elementen aus ${1,\dots,k}$.
 	p(n)=\sum_{k=1}^{n} p_k(n)&=p_n(2n)=\sum\limits_{k=1}^\infty(-1)^{k+1}\bigg[p\bigg(n - \frac{k(3k-1)}{2}\bigg) + p\bigg(n - \frac{k(3k+1)}{2}\bigg)\bigg]
 \end{align*}
 \begin{itemize}
+	\item $p(n)$: $1,~1,~2,~3,~5,~7,~11,~15,~22,~30,~42,~56,~77,~101,~135,~176,~231,~297,~385,~490,~627,~792$
 	\item in Formel $3$ kann abgebrochen werden wenn $\frac{k(3k-1)}{2} > n$.
 	\item Die Anzahl der Partitionen von $n$ in bis zu $k$ positive Summanden ist $\sum\limits_{i=0}^{k}p_i(n)=p_k(n+k)$.
 \end{itemize}
diff --git a/tcr.pdf b/tcr.pdf
index 392fbf0..808e1a3 100644
Binary files a/tcr.pdf and b/tcr.pdf differ
-- 
cgit v1.2.3


From 102e1dfaed9720ef2151288317903473506221d8 Mon Sep 17 00:00:00 2001
From: mzuenni <michi.zuendorf@gmail.com>
Date: Fri, 22 Aug 2025 18:21:28 +0200
Subject: added generating functions stuff

---
 content/math/math.tex                        |  38 ++++++++++++++++-----------
 content/math/transforms/seriesOperations.cpp |   6 ++---
 tcr.pdf                                      | Bin 700080 -> 701058 bytes
 3 files changed, 25 insertions(+), 19 deletions(-)

(limited to 'content/math/math.tex')

diff --git a/content/math/math.tex b/content/math/math.tex
index cb352f4..c303e85 100644
--- a/content/math/math.tex
+++ b/content/math/math.tex
@@ -418,8 +418,7 @@ $1,~1,~2,~5,~14,~42,~132,~429,~1430,~4862,~16796,~58786,~208012,~742900$
 \[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$ ohne Division in \runtime{n^2}, Formel $2$ und $3$ in \runtime{n}
 \end{itemize}
 
 \paragraph{\textsc{Catalan}-Convolution}
@@ -439,8 +438,7 @@ Dabei wird entweder ein Anstieg in zwei gesplitted oder ein Anstieg um $n$ ergä
 \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$ohne Division in \runtime{n^2}, Formel $2$ erlaubt Berechnung in \runtime{n\log(n)}
 \end{itemize}
 
 \paragraph{\textsc{Euler}-Zahlen 2. Ordnung:}
@@ -449,7 +447,7 @@ $|~1~|~1,~0~|~1,~2,~0~|~1,~8,~6,~0~|~1,~22,~58,~24,~0~|$
 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 ohne Division in \runtime{n^2}
 \end{itemize}
 
 \paragraph{\textsc{Stirling}-Zahlen 1. Ordnung:}
@@ -461,7 +459,7 @@ Es gibt zwei Möglichkeiten für die $n$-te Zahl. Entweder sie bildet einen eige
 \stirlingI{n}{0} = \stirlingI{0}{k} = 0 \qquad
 \stirlingI{n}{k} = \stirlingI{n-1}{k-1} + (n-1) \stirlingI{n-1}{k}\]
 \begin{itemize}
-	\item Formel erlaubt berechnung ohne Division in \runtime{n^2}
+	\item Formel ohne Division in \runtime{n^2}
 \end{itemize}
 \[\sum_{k=0}^{n}\pm\stirlingI{n}{k}x^k=x(x-1)(x-2)\cdots(x-n+1)\]
 \begin{itemize}
@@ -479,8 +477,7 @@ 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$ ohne Division in \runtime{n^2}, Formel $2$ in \runtime{n\log(n)}
 \end{itemize}
 
 \paragraph{\textsc{Bell}-Zahlen:}
@@ -488,24 +485,33 @@ $1,~1,~2,~5,~15,~52,~203,~877,~4140,~21147,~115975,~678570,~4213597$
 
 Anzahl der Partitionen von $\{1, \ldots, n\}$.
 Wie \textsc{Stirling}-Zahlen 2. Ordnung ohne Limit durch $k$.
+\vspace{-0.2cm}%
 \[B_0 = 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}\]
+\begin{itemize}
+	\item Alternative: $B(n) = \mathrm{EGF}\big(e^{e^n-1}\big)$ (\code{poly_exp} auf Seite \pageref{code:math/transforms/seriesOperations.cpp})
+\end{itemize}
 
-\paragraph{Partitions:}
+\paragraph{$\boldsymbol{k}$ Partitions:}
 $|~1~|~0,~1~|~0,~1,~1~|~0,~1,~1,~1~|~0,~1,~2,~1,~1~|~0,~1,~2,~2,~1,~1~|~0,~1,~3,~3,~2,~1,~1~|$
 
 Die Anzahl der Partitionen von $n$ in genau $k$ positive Summanden.
-Die Anzahl der Partitionen von $n$ mit Elementen aus ${1,\dots,k}$.
+Die Anzahl der Partitionen von $n$ mit größtem Elementen $k$.
 \begin{align*}
-	p_0(0)=1 \qquad p_k(n)&=0 \text{ für } k > n \text{ oder } n \leq 0 \text{ oder } k \leq 0\\
-	p_k(n)&= p_k(n-k) + p_{k-1}(n-1)\\[2pt]
-	p(n)=\sum_{k=1}^{n} p_k(n)&=p_n(2n)=\sum\limits_{k=1}^\infty(-1)^{k+1}\bigg[p\bigg(n - \frac{k(3k-1)}{2}\bigg) + p\bigg(n - \frac{k(3k+1)}{2}\bigg)\bigg]
+	p_0(0)=1 \qquad p_k(n)&=0 \text{ für } k > n \text{ oder } n \leq 0 \text{ oder } k \leq 0\\[-2pt]
+	p_k(n)&= p_k(n-k) + p_{k-1}(n-1)\\[-0.55cm]
 \end{align*}
 \begin{itemize}
-	\item $p(n)$: $1,~1,~2,~3,~5,~7,~11,~15,~22,~30,~42,~56,~77,~101,~135,~176,~231,~297,~385,~490,~627,~792$
-	\item in Formel $3$ kann abgebrochen werden wenn $\frac{k(3k-1)}{2} > n$.
-	\item Die Anzahl der Partitionen von $n$ in bis zu $k$ positive Summanden ist $\sum\limits_{i=0}^{k}p_i(n)=p_k(n+k)$.
+	\item Anzahl der Partitionen von $n$ in bis zu $k$ Summanden: $\sum\limits_{i=0}^{k}p_i(n)=p_k(n+k)$
+\end{itemize}
+
+\paragraph{Partitions:}
+$1,~1,~2,~3,~5,~7,~11,~15,~22,~30,~42,~56,~77,~101,~135,~176,~231,~297,~385,~490,~627$
+\[p(n)=\sum_{k=1}^{n} p_k(n)=p_n(2n)=\sum\limits_{k=1}^\infty(-1)^{k+1}\bigg[p\bigg(n - \frac{k(3k-1)}{2}\bigg) + p\bigg(n - \frac{k(3k+1)}{2}\bigg)\bigg]\]
+\begin{itemize}
+	\item Rekursion abbrechen wenn argument negativ wird $\Longrightarrow$ Laufzeit $\runtime{\sqrt{n}}$
+	\item Alternative: $p(n) = \mathrm{OGF(A)}^{-1}$ mit $A\mkern-1mu\big[\frac{k(3k\pm1)}{2}\big]\coloneqq(-1)^k$  (\code{poly_inv} auf Seite \pageref{code:math/transforms/seriesOperations.cpp})
 \end{itemize}
 
 \subsection{The Twelvefold Way \textnormal{(verteile $n$ Bälle auf $k$ Boxen)}}
diff --git a/content/math/transforms/seriesOperations.cpp b/content/math/transforms/seriesOperations.cpp
index b405698..d3e3072 100644
--- a/content/math/transforms/seriesOperations.cpp
+++ b/content/math/transforms/seriesOperations.cpp
@@ -1,4 +1,4 @@
-vector<ll> poly_inv(const vector<ll>& a, int n) {
+vector<ll> poly_inv(const vector<ll>& a, int n) { // a[0] == 1
 	vector<ll> q = {powMod(a[0], mod-2, mod)};
 	for (int len = 1; len < n; len *= 2){
 		vector<ll> a2 = a, q2 = q;
@@ -35,13 +35,13 @@ vector<ll> poly_integr(vector<ll> a) {
 	return a;
 }
 
-vector<ll> poly_log(vector<ll> a, int n) {
+vector<ll> poly_log(vector<ll> a, int n) { // a[0] == 1
 	a = mul(poly_deriv(a), poly_inv(a, n));
 	a.resize(n-1);
 	return poly_integr(a);
 }
 
-vector<ll> poly_exp(vector<ll> a, int n) {
+vector<ll> poly_exp(vector<ll> a, int n) { // a[0] == 0
 	vector<ll> q = {1};
 	for (int len = 1; len < n; len *= 2) {
 		vector<ll> p = poly_log(q, 2*len);
diff --git a/tcr.pdf b/tcr.pdf
index 808e1a3..4b8eab4 100644
Binary files a/tcr.pdf and b/tcr.pdf differ
-- 
cgit v1.2.3

