From 7d3908db71c6a49dc9853086090e500363c0c41b Mon Sep 17 00:00:00 2001
From: Paul Jungeblut <paul.jungeblut@gmail.com>
Date: Sun, 30 Oct 2016 10:13:34 +0100
Subject: Improving maths section.

---
 math/math.tex | 237 +++++++++++++++++++++++++++++++++++++++++-----------------
 1 file changed, 168 insertions(+), 69 deletions(-)

(limited to 'math/math.tex')

diff --git a/math/math.tex b/math/math.tex
index 6c20be2..e2cb565 100644
--- a/math/math.tex
+++ b/math/math.tex
@@ -110,9 +110,10 @@ Multipliziert Polynome $A$ und $B$.
 
 \subsection{Kombinatorik}
 
-\subsubsection{Berühmte Zahlen}
-\begin{tabular}{|l|l|}
-	\hline
+\begin{tabular}{ll}
+	\toprule
+	\multicolumn{2}{c}{Berühmte Zahlen} \\
+	\midrule 
 	\textsc{Fibonacci}	&
 	$f(0) = 0 \quad
 	f(1) = 1 \quad
@@ -142,80 +143,178 @@ Multipliziert Polynome $A$ und $B$.
 	\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{Int. Partitions} &
 	$f(1,1) = 1 \quad
 	f(n,k) = 0 \text{ für } k > n \quad
 	f(n,k) = f(n-k,k) + f(n,k-1)$ \\
-	\hline
+	\bottomrule
 \end{tabular}
 
-\begin{bem}[\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.
-\end{bem}
+\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.
 
-\begin{bem}[\textsc{Catalan}-Zahlen]
+\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 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}
+		\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{bem}
-
-\begin{bem}[\textsc{Euler}-Zahlen 1. Ordnung]
-	Die Anzahl der Permutationen von $\{1, \ldots, n\}$ mit genau $k$ Anstiegen.
-
-	Begründung: 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.
-	\end{bem}
-
-\begin{bem}[\textsc{Euler}-Zahlen 2. Ordnung]
-	Die Anzahl der Permutationen von $\{1,1, \ldots, n,n\}$ mit genau $k$ Anstiegen.
-\end{bem}
-
-\begin{bem}[\textsc{Stirling}-Zahlen 1. Ordnung]
-	Die Anzahl der Permutationen von $\{1, \ldots, n\}$ mit genau $k$ Zyklen.
-
-	Begründung: 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.
-\end{bem}
-
-\begin{bem}[\textsc{Stirling}-Zahlen 2. Ordnung]
-	Die Anzahl der Möglichkeiten $n$ Elemente in $k$ nichtleere Teilmengen zu zerlegen.
-
-	Begründung: 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.
-\end{bem}
-
-\begin{bem}[Bell-Zahlen]
-	Anzahl der Teilmengen von $\mathbb{N}$, die sich zu $n$ aufaddieren mit
-	maximalem Elment $\leq k$.
-\end{bem}
-
-\subsubsection{Verschiedenes}
-\begin{tabular}{|l|l|}
-	\hline
-	Türme von Hanoi, minimale Schirttzahl:					& $T_n = 2^n - 1$ \\
-	\#Regionen zwischen $n$ Gearden									& $n\left(n + 1\right) / 2 + 1$ \\
-	\#Abgeschlossene Regionen zwischen $n$ Geraden	& $\left(n^2 - 3n + 2\right) / 2$ \\
-	\#Markierte, gewurzelte Bäume										& $n^{n-1}$ \\
-	\#Markierte, nicht gewurzelte Bäume							& $n^{n-2}$ \\
-	\hline
+\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}
+
+\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{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$ \\
+
+	\#abgeschlossene 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}$ \\
+	\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}
 
 \subsection{Satz von \textsc{Sprague-Grundy}}
-- 
cgit v1.2.3

