diff options
Diffstat (limited to 'math/math.tex')
| -rw-r--r-- | math/math.tex | 20 |
1 files changed, 18 insertions, 2 deletions
diff --git a/math/math.tex b/math/math.tex index 8300ee4..1f1d542 100644 --- a/math/math.tex +++ b/math/math.tex @@ -39,6 +39,7 @@ Weise jedem Zustand $X$ wie folgt eine \textsc{Grundy}-Zahl $g\left(X\right)$ zu \] $X$ ist genau dann gewonnen, wenn $g\left(X\right) > 0$ ist.\\\\ Wenn man $k$ Spiele in den Zuständen $X_1, \ldots, X_k$ hat, dann ist die \textsc{Grundy}-Zahl des Gesamtzustandes $g\left(X_1\right) \oplus \ldots \oplus g\left(X_k\right)$. +\lstinputlisting{math/nimm.cpp} \subsection{Maximales Teilfeld} \lstinputlisting{math/maxTeilfeld.cpp} @@ -52,12 +53,17 @@ Obiger Code findet kein maximales Teilfeld, das über das Ende hinausgeht. Dazu: \subsection{Kombinatorik} \subsubsection{Berühmte Zahlen} +\begin{small} \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}\\ + \textsc{Fibonacci}-Zahlen & $f(0) = 0 \quad f(1) = 1 \quad f(n+2) = f(n+1) + f(n)$ & Bem. \ref{bem:fibonacciMat}, \ref{bem:fibonacciGreedy}\\ + \textsc{Catalan}-Zahlen & $C_0 = 1 \quad 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}$ & Bem. \ref{bem:catalanOverflow}, \ref{bem:catalanAnwendung}\\ + \textsc{Euler}-Zahlen (I) & $\left\langle\begin{array}{c} n \\ 0\end{array}\right\rangle = \left\langle\begin{array}{c} n \\ n-1 \end{array}\right\rangle = 1 \quad \left\langle\begin{array}{c} n \\ k\end{array}\right\rangle = (k + 1)\left\langle\begin{array}{c} n-1 \\ k\end{array}\right\rangle + (n-k)\left\langle\begin{array}{c} n-1 \\ k-1\end{array}\right\rangle$ & Bem. \ref{bem:euler1Intuition}\\ + \textsc{Euler}-Zahlen (II) & $\left\langle\left\langle\begin{array}{c}n\\0\end{array}\right\rangle\right\rangle = 1 \quad \left\langle\left\langle\begin{array}{c}n\\n\end{array}\right\rangle\right\rangle = 0 \quad \left\langle\left\langle\begin{array}{c}n\\k\end{array}\right\rangle\right\rangle = (k + 1)\left\langle\left\langle\begin{array}{c}n-1\\k\end{array}\right\rangle\right\rangle + (2n - k - 1)\left\langle\left\langle\begin{array}{c}n-1\\k-1\end{array}\right\rangle\right\rangle$ & Bem. \ref{bem:euler2Intuition}\\ + \textsc{Stirling}-Zahlen (I) & $\left[\begin{array}{c}0\\0\end{array}\right] = 1 \quad \left[\begin{array}{c}n\\0\end{array}\right] = \left[\begin{array}{c}0\\n\end{array}\right] = 0 \quad \left[\begin{array}{c}n\\k\end{array}\right] = \left[\begin{array}{c}n-1\\k-1\end{array}\right] + (n-1)\left[\begin{array}{c}n-1\\k\end{array}\right]$ & Bem. \ref{bem:stirling1}\\ \hline \end{tabular} +\end{small} \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)$ @@ -87,6 +93,16 @@ Die \textsc{Catalan}-Zahlen geben an: $C_n =$ \end{itemize} \end{bem} +\begin{bem}[\textsc{Euler}-Zahlen 1. Ordnung]\label{bem:euler1Intuition} +Die Anzahl der Permutationen von $\{1, \ldots, n\}$ mit genau $k$ Anstiegen. + +Die Formel folgt aus folgender Überlegung: 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]\label{bem:euler2Intuition} +Die Anzahl der Permutationen von $\{1,1, \ldots, n,n\}$ mit genau $k$ Anstiegen. +\end{bem} + \subsubsection{Verschiedenes} \begin{tabular}{|l|l|} \hline |