combinatorics: add some generating functions, remove (incorrect) 2nd order Eulerian numbers

2 files changed, 37 insertions, 46 deletions

diff --git a/content/latexHeaders/math.sty b/content/latexHeaders/math.sty
index d758f71..8219782 100644
--- a/content/latexHeaders/math.sty
+++ b/content/latexHeaders/math.sty
@@ -41,7 +41,7 @@
   \end{matrix}
   \Bigr)
 }
-% Euler numbers, first kind.
+% Eulerien numbers, first order.
 \newcommand{\eulerI}[2]{
   \Bigl\langle
   \begin{matrix}
@@ -50,15 +50,6 @@
   \end{matrix}
   \Bigr\rangle
 }
-% Euler numbers, second kind.
-\newcommand{\eulerII}[2]{
-  \Bigl\langle\mkern-4mu\Bigl\langle
-  \begin{matrix}
-    #1 \\
-    #2
-  \end{matrix}
-  \Bigr\rangle\mkern-4mu\Bigr\rangle
-}
 % Stirling numbers, first kind.
 \newcommand{\stirlingI}[2]{
   \Bigl[
diff --git a/content/math/math.tex b/content/math/math.tex
index f1eec86..7764d54 100644
--- a/content/math/math.tex
+++ b/content/math/math.tex
@@ -427,7 +427,7 @@ so gilt
 	\end{itemize}

 \end{itemize}

 \[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}\]

+\frac{1}{n + 1}\binom{2n}{n} = \frac{4n - 2}{n+1} C_{n-1} \sim \frac{4^n}{n^{3/2} \sqrt{\pi}}\]

 \begin{itemize}

 	\item Formel $1$ erlaubt Berechnung ohne Division in \runtime{n^2}

 	\item Formel $2$ und $3$ erlauben Berechnung in \runtime{n}

@@ -438,70 +438,70 @@ so gilt
 	\item Anzahl an Klammerausdrücken mit $n+k$ Klammerpaaren, die mit $(^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}\]

+\frac{k+1}{n+k+1}\binom{2n+k}{n} = \frac{(2n+k-1)(2n+k)}{n(n+k+1)} C_{n-1}\]

 

-\paragraph{\textsc{Euler}-Zahlen 1. Ordnung}

+\paragraph{\textsc{Euler}-Zahlen}

 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.

 \[\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)}

-\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}

-\end{itemize}

+\eulerI{n}{k} = (k+1) \eulerI{n-1}{k} + (n-k) \eulerI{n-1}{k-1}\]

+\[

+\eulerI{n}{k} = [x^k]

+	\left(\sum_{i=0}^\infty (i+1)^n x^i\right)

+	\left(\sum_{i=0}^\infty (-1)^i \binom{n+1}{i} x^i\right)

+\]

 

-\paragraph{\textsc{Stirling}-Zahlen 1. Ordnung}

+\paragraph{\textsc{Stirling}-Zahlen 1. Art}

 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.

+Es gibt zwei Möglichkeiten für die $n$-te Zahl. Entweder sie bildet einen eigenen 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}{k} = \stirlingI{n-1}{k-1} + (n-1) \stirlingI{n-1}{k}\]

-\begin{itemize}

-	\item Formel erlaubt berechnung 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}

-	\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$)

-\end{itemize}

+\[

+\stirlingI{n}{k}

+= [x^k]\prod_{i=0}^{n-1} (x+i)

+= n! [x^{n-k}] \frac{1}{k!} \left(\sum_{i=0}^\infty \frac{1}{i+1}x^i\right)^k

+\]

 

-\paragraph{\textsc{Stirling}-Zahlen 2. Ordnung}

+\paragraph{\textsc{Stirling}-Zahlen 2. Art}

 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}{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)}

-\end{itemize}

+\stirlingII{n}{k} = k \stirlingII{n-1}{k} + \stirlingII{n-1}{k-1}

+\]

+\[

+\stirlingII{n}{k}

+= [x^k]

+	\left(\sum_{i=0}^\infty \frac{i^n}{i!}x^i\right)

+	\left(\sum_{i=0}^\infty \frac{(-1)^i}{i!}x^i\right)

+= n! [x^{n-k}] \frac{1}{k!} \left(\sum_{i=0}^\infty \frac{1}{(i+1)!}x^i\right)^k

+\]

 

 \paragraph{\textsc{Bell}-Zahlen}

 Anzahl der Partitionen von $\{1, \ldots, n\}$.

-Wie \textsc{Stirling}-Zahlen 2. Ordnung ohne Limit durch $k$.

+Wie \textsc{Stirling}-Zahlen 2. Art 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}\]

+= \sum\limits_{k = 0}^{n}\stirlingII{n}{k}

+= n! [x^n] e^{e^x-1}

+\qquad

+B_{p^m+n}\equiv m\cdot B_n + B_{n+1} \bmod{p}\]

 

 \paragraph{Partitions}

 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*}

 	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_k(n)&= p_k(n-k) + p_{k-1}(n-1)\\

+	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(n)&=[x^n] \left(\sum_{k=-\infty}^\infty (-1)^k x^{k(3k-1)/2}\right)^{-1}

+	  \sim \frac{1}{4 \sqrt{3} n} \exp\left(\pi \sqrt{\frac{2n}{3}}\right)

 \end{align*}

 \begin{itemize}

 	\item in Formel $3$ kann abgebrochen werden wenn $\frac{k(3k-1)}{2} > n$.

+		$\rightarrow$ \runtime{n \sqrt{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}