diff options
Diffstat (limited to 'math')
| -rw-r--r-- | math/math.tex | 189 | ||||
| -rw-r--r-- | math/mobius.cpp | 4 | ||||
| -rw-r--r-- | math/phi.cpp | 8 |
3 files changed, 116 insertions, 85 deletions
diff --git a/math/math.tex b/math/math.tex index 1a4a684..7b2481d 100644 --- a/math/math.tex +++ b/math/math.tex @@ -158,6 +158,24 @@ Sei $p \geq 3$ eine Primzahl, $a \in \mathbb{Z}$: \end{align*} \lstinputlisting{math/legendre.cpp} +\subsection{\textsc{Möbius}-Funktion und \textsc{Möbius}-Inversion} +\begin{itemize} + \item Seien $f,g : \mathbb{N} \to \mathbb{N}$ und $g(n) := \sum_{d \vert n}f(d)$. + Dann ist $f(n) = \sum_{d \vert n}g(d)\mu(\frac{n}{d})$. + \item $\sum_{d \vert n}\mu(d) = + \begin{cases*} + 1 & falls $n = 1$\\ + 0 & sonst + \end{cases*}$ +\end{itemize} +\textbf{Beispiel Inklusion/Exklusion:} +Gegeben sein eine Sequenz $A={a_1,\ldots,a_n}$ von Zahlen, $1 \leq a_i \leq N$. Zähle die Anzahl der \emph{coprime subsequences}.\newline +\textbf{Lösung}: +Für jedes $x$, sei $cnt[x]$ die Anzahl der Vielfachen von $x$ in $A$. +Es gibt $2^{cnt[x]}-1$ nicht leere Subsequences in $A$, die nur Vielfache von $x$ enthalten. +Die Anzahl der Subsequences mit $\ggT=1$ ist gegeben durch $\sum_{i = 1}^N \mu(i) \cdot (2^{cnt[i]} - 1)$. +\lstinputlisting{math/mobius.cpp} + \subsection{Kombinatorik} \begin{flushleft} @@ -275,6 +293,68 @@ Anzahl der Teilmengen von $\mathbb{N}$, die sich zu $n$ aufaddieren mit maximale $\sum\limits_{i = 1}^n \binom{n}{i} F_i = F_{2n} \quad F_n = n\text{-th Fib.}$ \\ \bottomrule \end{tabular} +\vspace{1mm} + +\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} +\vspace{1mm} + +\begin{tabular}{l|r} + \toprule + \multicolumn{2}{c}{ + Wahrscheinlichkeitstheorie ($A,B$ Ereignisse und $X,Y$ Variablen) + } \\ + \midrule + $\E(X + Y) = \E(X) + \E(Y)$ & + $\E(\alpha X) = \alpha \E(X)$ \\ + + $X, Y$ unabh. $\Leftrightarrow \E(XY) = \E(X) \cdot \E(Y)$ & + $\Pr[A \vert B] = \frac{\Pr[A \land B]}{\Pr[B]}$ \\ + + $\Pr[A \lor B] = \Pr[A] + \Pr[B] - \Pr[A \land B]$ & + $\Pr[A \land B] = \Pr[A] \cdot \Pr[B]$ \\ + \bottomrule +\end{tabular} +\vspace{1mm} + +\begin{tabular}{lr|lr} + \toprule + \multicolumn{4}{c}{\textsc{Bertrand}'s Ballot Theorem (Kandidaten $A$ und $B$, $k \in \mathbb{N}$)} \\ + \midrule + $\#A > k\#B$ & $Pr = \frac{a - kb}{a + b}$ & + $\#B - \#A \leq k$ & $Pr = 1 - \frac{a!b!}{(a + k + 1)!(b - k - 1)!}$ \\ + + $\#A \geq k\#B$ & $Pr = \frac{a + 1 - kb}{a + 1}$ & + $\#A \geq \#B + k$ & $Num = \frac{a - k + 1 - b}{a - k + 1} \binom{a + b - k}{b}$ \\ + \bottomrule +\end{tabular} \vspace{5mm} \begin{tabular}{c|cccc} @@ -358,36 +438,36 @@ Anzahl der Teilmengen von $\mathbb{N}$, die sich zu $n$ aufaddieren mit maximale \end{flushleft} \vspace{1mm} -\begin{tabular}{l|r} +\begin{tabular}{ll} \toprule - \multicolumn{2}{c}{ - Wahrscheinlichkeitstheorie ($A,B$ Ereignisse und $X,Y$ Variablen) - } \\ + \multicolumn{2}{c}{Verschiedenes} \\ \midrule - $\E(X + Y) = \E(X) + \E(Y)$ & - $\E(\alpha X) = \alpha \E(X)$ \\ + Türme von Hanoi, minimale Schirttzahl: & + $T_n = 2^n - 1$ \\ - $X, Y$ unabh. $\Leftrightarrow \E(XY) = \E(X) \cdot \E(Y)$ & - $\Pr[A \vert B] = \frac{\Pr[A \land B]}{\Pr[B]}$ \\ + \#Regionen zwischen $n$ Gearden & + $\frac{n\left(n + 1\right)}{2} + 1$ \\ - $\Pr[A \lor B] = \Pr[A] + \Pr[B] - \Pr[A \land B]$ & - $\Pr[A \land B] = \Pr[A] \cdot \Pr[B]$ \\ - \bottomrule -\end{tabular} -\vspace{1mm} + \#geschlossene Regionen zwischen $n$ Geraden & + $\frac{n^2 - 3n + 2}{2}$ \\ -\begin{tabular}{lr|lr} - \toprule - \multicolumn{4}{c}{\textsc{Bertrand}'s Ballot Theorem (Kandidaten $A$ und $B$, $k \in \mathbb{N}$)} \\ - \midrule - $\#A > k\#B$ & $Pr = \frac{a - kb}{a + b}$ & - $\#B - \#A \leq k$ & $Pr = 1 - \frac{a!b!}{(a + k + 1)!(b - k - 1)!}$ \\ + \#markierte, gewurzelte Bäume & + $n^{n-1}$ \\ - $\#A \geq k\#B$ & $Pr = \frac{a + 1 - kb}{a + 1}$ & - $\#A \geq \#B + k$ & $Num = \frac{a - k + 1 - b}{a - k + 1} \binom{a + b - k}{b}$ \\ + \#markierte, nicht gewurzelte Bäume & + $n^{n-2}$ \\ + + \#Wälder mit $k$ gewurzelten Bäumen & + $\frac{k}{n}\binom{n}{k}n^{n-k}$ \\ + + Derangements & + $!n = (n - 1)(!(n - 1) + !(n - 2))$ \\ + & + $!n = \left\lfloor\frac{n!}{e} + \frac{1}{2}\right\rfloor$ \\ + & + $\lim\limits_{n \to \infty} \frac{!n}{n!} = \frac{1}{e}$ \\ \bottomrule \end{tabular} -\vspace{5mm} \begin{tabular}{p{4.3cm}|p{7cm}} \toprule @@ -485,67 +565,6 @@ Anzahl der Teilmengen von $\mathbb{N}$, die sich zu $n$ aufaddieren mit maximale Periode ab $n = 72$ der Länge $12$.\\ \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} -\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}$ \\ - - Dearangements & - $!n = (n - 1)(!(n - 1) + !(n - 2))$ \\ - & - $\lim\limits_{n \to \infty} \frac{!n}{n!} = \frac{1}{e}$ \\ - \bottomrule -\end{tabular} -\subsection{Big Integers} -\lstinputlisting{math/bigint.cpp} +% \subsection{Big Integers} +% \lstinputlisting{math/bigint.cpp} diff --git a/math/mobius.cpp b/math/mobius.cpp new file mode 100644 index 0000000..7830eb1 --- /dev/null +++ b/math/mobius.cpp @@ -0,0 +1,4 @@ +// Laufzeit: O(N*log(log(N))) +int mu[N+1]; mu[1] = 1; +for (int i = 1; i <= N; i++) { + for (int j = 2 * i; j <= N; j += i) mu[j] -= mu[i]; diff --git a/math/phi.cpp b/math/phi.cpp index 492a9d2..f568bba 100644 --- a/math/phi.cpp +++ b/math/phi.cpp @@ -10,3 +10,11 @@ ll phi(ll n) { // Laufzeit: O(sqrt(n)) if(n > 1) result -= result / n; return result; } + +// Sieb, falls alle Werte benötigt werden. Laufzeit: O(N*log(log(N))) +for (int i = 1; i <= N; i++) phi[i] = i; +for (int i = 2; i <= N; i++) if (phi[i] == i) { + for (int j = i; j <= N; j += i) { + phi[j] /= i; + phi[j] *= i - 1; +}} |