Transpositionen

Neue Frage »

14.12.2013, 11:16	Sandra88	Auf diesen Beitrag antworten »
Transpositionen Meine Frage: Hi! Ich habe die folgende Aufgabe und habe keine Ahnung, wie ich das zeigen soll. Es seien 1 $\begin{eqnarray} \leq \end{eqnarray}$ i < j $\begin{eqnarray} \leq \end{eqnarray}$ n $\begin{eqnarray} \in \end{eqnarray}$ N. Zeigen Sie, dass (i i+1)(i+1 i+2) . . . (j-2 j-1)(j-1 j)(j-1 j-2) . . . (i+1 i) = (ij) ist (z.B. ist (34)(45)(56)(67)(65)(54)(43) = (37) ). Schließen Sie daraus, dass jede Permutation in Sn das Produkt von Transpositionen der Form (l l+1), 1 $\begin{eqnarray} \leq \end{eqnarray}$ l < n, ist. Meine Ideen: Ich verstehe, dass man jede Permutation als Produkt paarweiser disjunkter Zyklen schreiben kann und auch, dass man jeden Zykel wieder als Produkt von Transpositionen schreiben kann. Also jede Permutation als Produkt von Transpositionen. Beispiel: Ich kann die Permutation $\begin{eqnarray} \begin{pmatrix} 1& 2& 3&4 \\ 4& 3 & 1&2 \end{pmatrix} \end{eqnarray}$ schreiben als $\begin{eqnarray} \left(1423\right) \end{eqnarray}$ Und das wiederum als (14) (42) (23) oder (13) (12) (14). Ich versteh also, warum es geht, nur das Beweisen liegt mir überhaupt nicht!
14.12.2013, 11:26	Elvis	Auf diesen Beitrag antworten »
Schön, dass du das "verstehst". Ich verstehe nicht, wie "verstehen" ohne "beweisen" funktioniert. "Glaubst" du alles, was gesagt oder geschrieben wird ? Der Beweis schreit nach vollständiger Induktion.
14.12.2013, 12:04	Sandra88	Auf diesen Beitrag antworten »
Transpositionen Is ja total lieb von dir, dass du mich gleich so angreifst! ok! Dann versteh ich es hald nicht! Wie ich da einen induktionsbeweis mache, versteh ich erst recht nicht! also: (i i+1) o (j-2 j-1)o (j-1 j) o(j-1 j-2)o(i+1 i)=(ij) i=1 j=4 : (12)o(23)o(34)o(32)o(21)=(14) --> stimmt Z.z. (i+1 i+2) o (j-1 j)o (j j+1) o(j j-1)o(i+2 i+1)=(i+1j+1) Hab keine Ahnung!! Mache das glaub ich total falsch!!
14.12.2013, 14:31	Elvis	Auf diesen Beitrag antworten »
"Selbsterkenntnis ist der erste Weg zu Besserung." Tipp 1: Ich würde vollständige Induktion nach j-i versuchen. Tipp 2: Für den letzten Schluß brauchst du nur noch die Gleichheit (a b)=(b a) benutzen.
14.12.2013, 15:38	Sandra88	Auf diesen Beitrag antworten »
Sowas hab ich noch nie gemacht! wir haben immer nur ganz leichte induktionsbeweise gemacht. Zum Beispiel die Gaußsche Summenformel beweisen oder so. Hab da überhaupt keine Ahnung wie ich das machen soll!
15.12.2013, 10:07	Sandra88	Auf diesen Beitrag antworten »
Ich hab mir jetzt einige solcher Transpositionen aufgeschrieben und hab "herausgefunden", dass diese immer ungerade sind und, dass ich i schreiben kann als $\begin{eqnarray} j-\frac{n+1}{2} \end{eqnarray}$ und j kann ich schreiben als $\begin{eqnarray} i+\frac{n+1}{2} \end{eqnarray}$ . Die Anzahl der Transpositionen, also das n, ergib sich aus ((j-i)*2)-1. Nützt mir das was, dass ich keinen induktionsbeweis machen muss??Dass kann ich nicht!!
Anzeige

15.12.2013, 11:07	Elvis	Auf diesen Beitrag antworten »
Das ist leider falsch, also nützt es nichts. Wenn du z.B. i=2 mit j=5 vertauschen willst, kann n=1000 oder n=53542346 sein, deine Formel macht in keinem Fall irgendeinen Sinn. Wenn du Mathematik lernen möchtest, musst du mit Beweisen anfangen. Das Prinzip der vollständigen Induktion ist kein Problem, sondern ein sehr nützliches Beweisprinzip. Vorschlag: Mache den (Induktions-)Anfang mit j-i=1. Mache dir dann Gedanken zum Induktionsschritt, z.B. kannst du darüber nachdenken, was sich verändert, wenn du 2 und 6 anstatt 2 und 5 miteinander vertauschen möchtest ... berücksichtige meinen Tipp 2, dann wird das Vertauschen durch Transpositionen vielleicht etwas übersichtlicher. Noch ein Hinweis: Der dritte Teil von Peter Jacksons Film "Der Hobbit" (2014) hat den Titel "Hin und zurück".
15.12.2013, 12:34	Sandra88	Auf diesen Beitrag antworten »
Danke erstmal! Also, dass sich nach dem (j-1 j) alles umdreht habe schon von Anfang an gesehen, aber wie du sagtest, nützt mir das nichts ohne den beweis! Dieses (j-1 j) ist also wahrscheinlich wichtig!! Hab das jetzt mal versucht! Bitte nicht lachen: (i i+1)(i+1 i+2) . . . (j-2 j-1)(j-1 j)(j-1 j-2) . . . (i+1 i) = (ij) j-i=1 (ij)(j i+2)...(j-2 i) (ij)(i j-2)...(ji)=(j-1 i+1) Der Unterschied zwischen (2 5) und (2 6) ist, dass sich dieses (j-1 j) genau um 1 verschiebt und dadurch nochmal eine "Umkehrung" dazu kommt! Ich hoffe du verstehst was ich meine! Vor und hinter dem (j-1 j) steht immer das gleiche, da ja (ab) =(ba)! Das was da davor und dahinter steht, ist genau (i j-1) Also z.b bei (26) steht vor (56),(25)und danach auch! Ich bin aber immer noch zu doof um das irgendwie zu verwenden!!!
15.12.2013, 18:27	Elvis	Auf diesen Beitrag antworten »
Induktionsanfang: Der Algorithmus , den du angibst, reduziert sich für j=i+1 auf (i j) . FERTIG. Besser kann ich's leider nicht erklären, das ist so einfach, wie es aussieht. Induktionsschritt: Mein Hinweis mit dem "hin und zurück" nützt dir besonders dann etwas, wenn du mal einige Beispiel durchrechnest. Der Algorithmus zerfällt offensichtlich in 2 Teile. Im ersten Teil wird i, i+1, .. durch Transpositionen jeweils eine Stelle nach rechts geschoben und j landet an der Stelle i. (Man sieht das sehr schön an der Diagonale 2,3,4,5 im Beispiel.) Im zweiten Teil wird von der Stelle j her alles bis zur Stelle i+1 rückgängig gemacht, dadurch landet in einem Schritt weniger i an der Stelle j, weil i schon im 1. Teil um 1 nach rechts gerückt war. (Das sieht man im Beipiel in der letzten Spalte 5,4,3,2. ) Jetzt klar ? Wenn du möchtest, kannst du das sicher noch formaler als richtigen Induktionsbeweis aufschreiben. Mir genügt hier, dass ich nach stundenlanger Analyse "verstanden" habe, wie die Sache funktioniert. Als Beispiel dient mir $\begin{eqnarray} (26)=(23)(34)(45)(56)(54)(43)(32), \end{eqnarray}$ was sich auch so schreiben lässt: $\begin{eqnarray} \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ & 3 & 2 & \\ & 4 & & 3 \\ & 5 & & & 4 \\ & 6 & & & & 5 \\ & & & & 5 & 4 \\ & & & 4 & & 3 \\ & & 3 & & & 2 \end{pmatrix} \end{eqnarray}$
16.12.2013, 19:06	Elvis	Auf diesen Beitrag antworten »
Nach weiterem Nachdenken behaupte ich einfach mal, dass o.B.d.A. i=1 gesetzt werden kann - für i>1 bleibt alles kleiner als i bei allen Transpositionen unverändert, d.h. das Spiel findet lediglich weiter rechts statt - also genügt schlicht und einfach eine vollständige Induktion nach j für j>=2 .
17.12.2013, 09:59	Sandra88	Auf diesen Beitrag antworten »
Hi! Vielen Dank erstmal! Gemacht hab ich es dann so: IB: (34) (45) (56)(67)(65)(54)(43) IA: (i i+1)(i+1 i+2) . . . (j-2 j-1)(j-1 j)(j-1 j-2) . . . (i+1 i) = (ij) Z.z: (i-1,i) (i i+1)(i+1 i+2) . . . (j-2 j-1)(j-1 j)(j-1 j-2) . . . (i+1 i) (i,i-1) IA (i-1,i) (ij) (i,i-1)= (j,i-1) das hat mir jemand gezeigt und erklärt. Ich "versteh" jetzt auch, warum ich die Induktion nach j-i nicht verstanden habe. Wir haben immer nur Induktionen gemacht, bei denen wir von n auf n+1 gegangen sind. Die umgekehrte Variante hatten wir nie gemacht und daher war das für mich unverständlich. Mir ist bewusst, dass meine induktion einen kleinen Haken hat, (i=1) nur versteh ich es hald so besser! Ich gebe eine Permutation dazu und muss zeigen, dass es dann immer noch gilt... War für mich einfach verständlicher. Ich danke dir aber trotzdem für deine Hilfe. :-)
17.12.2013, 10:00	Sandra88	Auf diesen Beitrag antworten »
Das IA hat sich verschoben, es sollte in der Mitte stehen! ;-)
17.12.2013, 18:30	Elvis	Auf diesen Beitrag antworten »
Deinen Beweis verstehe ich leider nicht, er scheint mir sehr "unvollständig" zu sein, was insbesondere für eine "vollständige Induktion" sehr schade ist. Den Hinweis, dass man den Beweis auf eine vollständige Induktion über j führen kann, indem man o.B.d.A. i=1 setzt, hast Du übrigens von mir bekommen, in Deinem Beweisversuch tritt das gar nicht auf.

Neue Frage »

Antworten »

Transpositionen

Verwandte Themen