bissl Kombinatorik

6 files changed, 55 insertions, 5 deletions

diff --git a/graph/graph.tex b/graph/graph.tex
index 8d525f6..98d5ffd 100644
--- a/graph/graph.tex
+++ b/graph/graph.tex
@@ -66,6 +66,6 @@ Finde die maximale Anzahl Pfade von $s$ nach $t$, die keinen Knoten teilen.
 	\item Der maximale Fluss entspricht der unterschiedlichen Pfade ohne gemeinsame Knoten.
 \end{enumerate}
 
-\subsubsection{Maximal Cardinatlity Bipartite Mathcing}
+\subsection{Maximal Cardinatlity Bipartite Mathcing}
 \lstinputlisting{graph/maxCarBiMatch.cpp}
 
diff --git a/math/math.tex b/math/math.tex
index feb89ff..8300ee4 100644
--- a/math/math.tex
+++ b/math/math.tex
@@ -49,3 +49,51 @@ Obiger Code findet kein maximales Teilfeld, das über das Ende hinausgeht. Dazu:
 	\item nimm Maximum aus gefundenem Maximalem und Allem\textbackslash Minimalem
 \end{enumerate}
 
+\subsection{Kombinatorik}
+
+\subsubsection{Berühmte Zahlen}
+\begin{tabular}{|l|l|l|}
+	\hline
+	\textsc{Fibonacci}	& $f(0) = 0 \quad f(1) = 1 \quad f(n+2) = f(n+1) + f(n)$	& siehe Bemerkungen \ref{bem:fibonacciMat}, \ref{bem:fibonacciGreedy}\\
+	\textsc{Catalan}	& $C_n = \sum\limits_{k = 0}^{n - 1} C_kC_{n - 1 - k} = \frac{1}{n + 1}{2n \choose n} = \frac{2(2n - 1)}{n+1} \cdot C_{n-1}$	& siehe Bemerkungen \ref{bem:catalanOverflow}, \ref{bem:catalanAnwendung}\\
+	\hline
+\end{tabular}
+
+\begin{bem}\label{bem:fibonacciMat}
+$\left(\begin{array}{cc} 0 & 1 \\ 1 & 1\end{array}\right)^n \cdot \left(\begin{array}{c}0 \\ 1\end{array}\right) = \left(\begin{array}{c}f_n \\ f_{n+1}\end{array}\right)$
+\end{bem}
+
+\begin{bem}[\textsc{Zeckendorfs} Theorem]\label{bem:fibonacciGreedy}
+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}
+
+\begin{bem}\label{bem:catalanOverflow}
+\begin{itemize}
+	\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.
+\end{itemize}
+\end{bem}
+
+\begin{bem}\label{bem:catalanAnwendung}
+Die \textsc{Catalan}-Zahlen geben an: $C_n =$
+\begin{itemize}
+	\item Anzahl der Binärbäume mit $n$ 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 in einem $n \times n$-Gitter, die nicht die Diagonale kreuzen. (zwischen gegenüberliegenden Ecken)
+\end{itemize}
+\end{bem}
+
+\subsubsection{Verschiedenes}
+\begin{tabular}{|l|l|}
+	\hline
+	Hanoi Towers (min steps)		& $T_n = 2^n - 1$\\
+	regions by $n$ lines			& $n\left(n + 1\right) / 2 + 1$\\
+	bounded regions by $n$ lines		& $\left(n^2 - 3n + 2\right) / 2$\\
+	labeled rooted trees			& $n^{n-1}$\\
+	labeled unrooted trees			& $n^{n-2}$\\
+	\hline
+\end{tabular}
\ No newline at end of file
diff --git a/sonstiges/sonstiges.tex b/sonstiges/sonstiges.tex
index 1a51ad9..375dc6b 100644
--- a/sonstiges/sonstiges.tex
+++ b/sonstiges/sonstiges.tex
@@ -9,7 +9,7 @@
 \end{enumerate}
 
 \subsection{Sortieren in Linearzeit}
-Wenn die Eingabe aus einem kleinen Intervall $\left[0, n\right)$ stammt ist Bucketsort \lstinline{bucketSort(vector<int> ..., n);} schneller.
+Wenn die Eingabe aus einem kleinen Intervall $\left[0, n\right)$ stammt ist Bucketsort schneller.
 
 \subsubsection{Bucketsort}
 \lstinputlisting{sonstiges/bucketSort.cpp}
diff --git a/tcr.pdf b/tcr.pdf
index c72ebaa..4a847fe 100644
--- a/tcr.pdf
+++ b/tcr.pdf
diff --git a/tcr.tex b/tcr.tex
index 58a8f25..cbdb2e6 100644
--- a/tcr.tex
+++ b/tcr.tex
@@ -47,6 +47,9 @@
 \usepackage[top=2cm, bottom=2cm, left=2cm, right=1cm]{geometry}
 
 \usepackage{multicol}
+\usepackage{multirow}
+
+\newtheorem{bem}{Bemerkung}
 
 \title{Team Contest Reference}
 \author{ChaosKITs \\ Karlsruhe Institute of Technology}
diff --git a/toDo.txt b/toDo.txt
index 1eb60b3..3395f15 100644
--- a/toDo.txt
+++ b/toDo.txt
@@ -1,7 +1,6 @@
-- mathe formeln, kombinatorik (catalan, stirling, euler, ...)
 - bitonic tsp
 - josephus problem
 - min cost max flow
 - roman numerals
-- towers of hanoi
-- NIM GAMES (WICHTIG)
\ No newline at end of file
+- NIM GAMES (WICHTIG)
+- bit operationen (WICHTIG)
\ No newline at end of file