2 files changed, 23 insertions, 0 deletions
diff --git a/math/math.tex b/math/math.tex
index 1a4a684..7ba72b9 100644
--- a/math/math.tex
+++ b/math/math.tex
@@ -158,6 +158,25 @@ 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}
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];