From 678969a72ce687ffdfcb64e9ec8a2f60ad7266c9 Mon Sep 17 00:00:00 2001
From: Florian Forster <octo@leeloo.octo.it>
Date: Thu, 27 Jan 2011 16:04:43 +0100
Subject: [PATCH] k-Schnittmuster: Verwende k=n-m statt m.

---
 diplomarbeit.tex | 36 +++++++++++++++++++-----------------
 1 file changed, 19 insertions(+), 17 deletions(-)

diff --git a/diplomarbeit.tex b/diplomarbeit.tex
index 9c316c4..25d6329 100644
--- a/diplomarbeit.tex
+++ b/diplomarbeit.tex
@@ -871,8 +871,10 @@ Der Eliminierungsschritt kann iterativ angewandt werden, um aus einem
 Sortiernetzwerk mit $n$~Ein\-gängen Sortiernetzwerke mit $n-1$, $n-2$,
 $n-3$,~\dots Eingängen zu erzeugen. Insbesondere können auf diese Art und
 Weise einen Sortiernetzwerke mit $2n$~Eingängen wieder auf Sortiernetzwerke
-mit $n$~Eingängen reduziert werden. Mehrere Minimum- und Maximum-Schnitte, die
-gleichzeitig angewendet werden, bezeichnen wir als \emph{Schnittmuster}.
+mit $n$~Eingängen reduziert werden. $k$~Minimum- und Maximum-Schnitte, die
+nacheinander angewendet ein $n$-Sortiernetzwerk auf ein
+${(n-k)}$-Sortiernetz\-werk reduzieren, bezeichnen wir als
+\emph{$k$-Schnittmuster}.
 
 Zwei Schnittmuster heißen \emph{äquivalent} bezüglich~$S$, wenn ihre Anwendung
 auf das Sortiernetzwerk~$S$ das selbe Ergebnis liefert. Ansonsten heißen die
@@ -881,10 +883,10 @@ Schnittmuster \emph{unterschiedlich} bezüglich~$S$.
 Bei einem Sortiernetzwerk mit $n$~Eingängen gibt es $2n$~Möglichkeiten eine
 Leitung zu entfernen: Auf jeder der $n$~Leitungen kann sowohl das Minimum als
 auch das Maximum angenommen werden. Wendet man das Verfahren iterativ an, um
-ein $n$-Sortiernetzwerk auf ein $m$-Sortiernetzwerk zu reduzieren, ergeben
-sich insgesamt
+ein $n$-Sortiernetzwerk auf ein ${(n-k)}$-Sortiernetzwerk zu reduzieren,
+ergeben sich insgesamt
 \begin{equation}\label{eqn:anzahl_schnittmuster}
-  \prod_{i=n}^{m+1} 2i = 2^{n-m} \frac{n!}{m!}
+  \prod_{i=n}^{1+n-k} 2i = 2^k \frac{n!}{(n-k)!}
   \quad (n > m)
 \end{equation}
 \emph{mögliche} Schnittmuster. Diese Schnittmuster sind nicht alle
@@ -892,19 +894,19 @@ unterschiedlich. Legt man beispielsweise das Minimum auf die unterste Leitung
 und das Maximum auf die oberste Leitung eines Standard-Sortiernetzwerks,
 führen beide Reihenfolgen zum selben Ergebnis.
 
-\textit{Moritz Mühlenthaler} zeigt in seiner Arbeit (\todo{Referenz}), dass
-es möglich ist, mehrere Eingänge gleichzeitig mit Minimum beziehungsweise
-Maximum vorzubelegen. Dadurch wird die Anzahl der möglichen Schnittmuster
-reduziert, die Menge der so erzeugbaren Sortiernetzwerke bleibt aber
-unverändert. Die Anzahl der möglichen Schnittmuster setzt sich zusammen aus
-der Anzahl von Möglichkeiten, $n-m$~Leitungen aus $n$ Leitungen auszuwählen,
-und die möglichen Minimum-~/ Maximum-Muster. Damit ergibt sich folgende
-Formel für die Anzahl der Schnittmuster:
+\textit{Moritz Mühlenthaler} zeigt in seiner Arbeit (\todo{Referenz}), dass es
+möglich ist, mehrere Eingänge gleichzeitig mit Minimum beziehungsweise Maximum
+vorzubelegen. Dadurch wird die Anzahl der möglichen Schnittmuster reduziert,
+die Menge der so erzeugbaren Sortiernetzwerke bleibt aber unverändert. Die
+Anzahl der möglichen Schnittmuster setzt sich zusammen aus der Anzahl von
+Möglichkeiten, $k$~Leitungen aus $n$~Leitungen auszuwählen, und die möglichen
+Minimum-~/ Maximum-Muster. Damit ergibt sich folgende Formel für die Anzahl
+der möglichen Schnittmuster:
 \begin{displaymath}
-  2^{n-m} \cdot \left( \begin{array}{c} n \\ n-m \end{array} \right)
-  = 2^{n-m} \cdot \frac{n!}{(n-m)! m!}
-  = 2^{n-m} \cdot \frac{n!}{m!} \cdot \frac{1}{(n-m)!}
-  \quad (n > m)
+  2^k \cdot \left( \begin{array}{c} n \\ k \end{array} \right)
+  = 2^{k} \cdot \frac{n!}{k! (n-k)!}
+  = 2^{k} \cdot \frac{n!}{(n-k)!} \cdot \frac{1}{k!}
+  \quad (1 \leqq k < n)
 \end{displaymath}
 
 Die Anzahl der möglichen Schnittmuster wird mit der Anzahl der zu entfernenden
-- 
2.11.0