From 4b48621b48d3248b5e2718a10e35e7276c504a72 Mon Sep 17 00:00:00 2001
From: Paul Jungeblut <paul.jungeblut@gmail.com>
Date: Sun, 22 Oct 2017 19:48:13 +0200
Subject: Adding code for Möbius Inversion.
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

---
 math/math.tex | 19 +++++++++++++++++++
 1 file changed, 19 insertions(+)

(limited to 'math/math.tex')

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}
-- 
cgit v1.2.3