diff options
Diffstat (limited to 'math/math.tex')
| -rw-r--r-- | math/math.tex | 55 |
1 files changed, 45 insertions, 10 deletions
diff --git a/math/math.tex b/math/math.tex index 7093f78..51410bd 100644 --- a/math/math.tex +++ b/math/math.tex @@ -66,20 +66,55 @@ Multipliziert Polynome $A$ und $B$. \subsection{Kombinatorik} \subsubsection{Berühmte Zahlen} -\begin{tabular}{|l|l|l|} +\begin{tabularx}{\textwidth}{|l|X|l|} \hline - \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:euler1}\\ - \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:euler2}\\ - \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}\\ - \textsc{Stirling}-Zahlen (II) & $\left\{\begin{array}{c}n\\1\end{array}\right\} = \left\{\begin{array}{c}n\\n\end{array}\right\} = 1 \quad \left\{\begin{array}{c}n\\k\end{array}\right\} = k\left\{\begin{array}{c}n-1\\k\end{array}\right\} + \left\{\begin{array}{c}n-1\\k-1\end{array}\right\}$ & Bem. \ref{bem:stirling2}\\ - Integer-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)$ & Bem. \ref{bem:integerPartitions}\\ + \textsc{Fibonacci}-Zahlen & + $f(0) = 0 \qquad + f(1) = 1 \qquad + f(n+2) = f(n+1) + f(n)$ & + Bem. \ref{bem:fibonacciMat}, \ref{bem:fibonacciGreedy} \\ + + \textsc{Catalan}-Zahlen & + $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{2(2n - 1)}{n+1} \cdot C_{n-1}$ & + Bem. \ref{bem:catalanOverflow}, \ref{bem:catalanAnwendung} \\ + + \textsc{Euler}-Zahlen (I) & + $\eulerI{n}{0} = \eulerI{n}{n-1} = 1 \qquad + \eulerI{n}{k} = (k+1) \eulerI{n-1}{k} + (n-k) \eulerI{n-1}{k-1} $ & + Bem. \ref{bem:euler1} \\ + + \textsc{Euler}-Zahlen (II) & + $\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}$ & + Bem. \ref{bem:euler2} \\ + + \textsc{Stirling}-Zahlen (I) & + $\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}$ & + Bem. \ref{bem:stirling1} \\ + + \textsc{Stirling}-Zahlen (II) & + $\stirlingII{n}{1} = \stirlingII{n}{n} = 1 \qquad + \stirlingII{n}{k} = k \stirlingII{n-1}{k} + \stirlingII{n-1}{k-1}$ & + Bem. \ref{bem:stirling2} \\ + + Integer-Partitions & + $f(1,1) = 1 \qquad f(n,k) = 0 \text{ für } k > n \qquad f(n,k) = f(n-k,k) + f(n,k-1)$ & + Bem. \ref{bem:integerPartitions} \\ \hline -\end{tabular} +\end{tabularx} \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)$ +$ +\begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}^n +\cdot +\begin{pmatrix} 0 \\ 1 \end{pmatrix} += +\begin{pmatrix}f_n \\ f_{n+1} \end{pmatrix} +$ \end{bem} \begin{bem}[\textsc{Zeckendorfs} Theorem]\label{bem:fibonacciGreedy} |