Effekt einer Nachbartransposition

06.05.2009, 11:08	Felix	Auf diesen Beitrag antworten »
Effekt einer Nachbartransposition Sei $\begin{eqnarray} \pi \end{eqnarray}$ eine beliebige Permutation einer Menge $\begin{eqnarray} X \end{eqnarray}$ und $\begin{eqnarray} \tau \end{eqnarray}$ eine Nachbartransposition dieser Menge. Dann ist $\begin{eqnarray} f(\tau \pi) = f(\pi) \pm 1 \end{eqnarray}$ . $\begin{eqnarray} f(x) \end{eqnarray}$ gibt die Anzahl der Fehlstände einer Permutation x an. Den Beweis habe ich mir gerade selbst klar gemacht, so wie er in meinem Buch steht halte ich ihn nämlich für falsch: a) Sei das Paar $\begin{eqnarray} (i, i+1) \end{eqnarray}$ ein Fehlstand von $\begin{eqnarray} \pi \end{eqnarray}$ , dann hebt die Multiplikation von $\begin{eqnarray} \pi \end{eqnarray}$ mit $\begin{eqnarray} \tau \end{eqnarray}$ diesen Fehlstand auf. Das ist doch falsch: Angenommen $\begin{eqnarray} \pi(i) = k \neq i,i+1 \end{eqnarray}$ und $\begin{eqnarray} \pi(i+1) = q \neq i,i+1 \end{eqnarray}$ mit $\begin{eqnarray} k>q \end{eqnarray}$ . Dann ist $\begin{eqnarray} (i,i+1) \end{eqnarray}$ ein Fehlstand wird aber nicht durch die Multiplikation mit $\begin{eqnarray} \tau \end{eqnarray}$ aufgehoben, da $\begin{eqnarray} \tau \end{eqnarray}$ die Elemente $\begin{eqnarray} q \end{eqnarray}$ und $\begin{eqnarray} k \end{eqnarray}$ unberührt lässt. b) "folgt" so ähnlich ... Habe ich nur etwas nicht beachtet, oder denkt ihr auch, dass dieser Beweis nicht richtig geführt ist ? lg
25.12.2012, 17:58	1=0!	Auf diesen Beitrag antworten »
Tut mir leid dass ich dieses Thema wieder herrausgrabe, ich bin aber auf dasselbe Problem gestoßen. Ich nehme an der Autor bezieht sich das Buch von Albrecht Beutelspacher.
26.12.2012, 01:55	RavenOnJ	Auf diesen Beitrag antworten »
Die Aussage in dem Buch ist richtig. Sei $\begin{align} \sigma \end{align}$ eine Permutation, dann ist das Signum der Permutation gegeben durch $\begin{eqnarray} sig(\sigma) = (-1)^{f(\sigma)} \end{eqnarray}$ mit der Zahl der Fehlstände $\begin{align} f(\sigma) \end{align}$ . Sei $\begin{align} \tau \end{align}$ eine beliebige Transposition. Durch eine Transposition ändert das Signum das Vorzeichen, d.h. $\begin{eqnarray} sig(\tau\pi) = (-1)^{f(\tau\pi)}= -sig(\pi) = -(-1)^{f(\pi)} \end{eqnarray}$ Der Fehlstand von $\begin{align} \tau\pi \end{align}$ unterscheidet sich also vom Fehlstand von $\begin{align} \pi \end{align}$ um eine ungerade Zahl. Wenn es sich aber bei $\begin{align} \tau \end{align}$ um eine Nachbartransposition handelt, dann kann der Betrag des Fehlstandes sich um höchstens $\begin{align} 1 \end{align}$ ändern. Daraus folgt: $\begin{eqnarray} f(\tau\pi) = f(\pi) \pm 1 \end{eqnarray}$ (Man könnte auch direkt zeigen, dass der Fehlstand sich bei einer Nachbartransposition um $\begin{align} \pm 1 \end{align}$ ändern muss, da nur der Fehlstand der vertauschten Elemente sich ändert, in Relation zu den anderen Elementen ändert sich jedoch nichts.)

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »