From ddd6805b49d7b4d6e36445ffac00bef55dbc9c86 Mon Sep 17 00:00:00 2001 From: mzuenni 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 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 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 poly_inv(const vector& a, int n) { +vector poly_inv(const vector& a, int n) { // a[0] == 1 vector q = {powMod(a[0], mod-2, mod)}; for (int len = 1; len < n; len *= 2){ vector a2 = a, q2 = q; @@ -35,13 +35,13 @@ vector poly_integr(vector a) { return a; } -vector poly_log(vector a, int n) { +vector poly_log(vector a, int n) { // a[0] == 1 a = mul(poly_deriv(a), poly_inv(a, n)); a.resize(n-1); return poly_integr(a); } -vector poly_exp(vector a, int n) { +vector poly_exp(vector a, int n) { // a[0] == 0 vector q = {1}; for (int len = 1; len < n; len *= 2) { vector 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