Permutationen erzeugen

02.01.2023, 11:30

Weduschij

Permutationen erzeugen

Meine Frage:
Zeige, dass Sn von dem n-Zykel (1 2 . . . n) und der Transposition (1 2) erzeugt wird, d.h.
es gilt Sn = [ (1 2 . . . n),(1 2) ].
Hinweis: Bestimme (1 2 . . . n) ? (1 2) ? (1 2 . . . n)^-1

Meine Ideen:
Also ich weiß dass man mit (1,2,3...,n) * (1,2) viele Permuationen erzeugen kann. Und mithilfe des Hinweises hab ich herausgefunden, dass die 2 immer mit der Zahl rechts von sich die Plätze "tauscht". Was ich nicht verstehe ist, wie ich das zeigen soll.

02.01.2023, 12:34

HAL 9000

Auf diesen Beitrag antworten »

Hast du denn mal (wie empfohlen) $\begin{eqnarray*} (1~2~\ldots~n)\circ (1~2) \circ (1~2~\ldots~n)^{-1} \end{eqnarray*}$ ausgerechnet? Resultat ist $\begin{eqnarray*} (2~3) \end{eqnarray*}$ .

Sukzessive bekommt man mit dieser Idee alle Transpositionen benachbarter Elemente, d.h., $\begin{eqnarray*} (k~k\!+\!1) \end{eqnarray*}$ für alle $\begin{eqnarray*} k=1,\ldots,n-1 \end{eqnarray*}$ bis hin zu $\begin{eqnarray*} (n~1) \end{eqnarray*}$ .

Eine Ahnung, wie es mit diesem Resultat dann weiter gehen könnte? Wenn du z.B. zeigen könntest, dass man damit alle Transpositionen konstruieren kann...

02.01.2023, 12:46

Weduschij

Auf diesen Beitrag antworten »

Mein Ziel ist es ja mit Hilfe von (1,2) und (1,2,3,..,n). Beim Hinweis wird ja (1,n,n-1,...,2) benutzt. Wie komme ich denn mit Hilfe von den zwei Permutationen auf die "Umkehr" Permutation? Und sagen wir mal dann ich habe die Transpositionen (1,2),(2,3) ...(n,1). Dann hab ich ja den Zykel (1,2,3,..n). Aber irgendwie scheint es mir so als ob ich hier irgendwo ein Verständnisproblem habe.

02.01.2023, 12:48

HAL 9000

Auf diesen Beitrag antworten »

Dir ist doch sicher bekannt, dass man jeden Zykel (und damit mittelbar auch jede Permutation) als Produkt von Transpositionen darstellen kann?

Insofern ist man doch am Ziel, wenn man das hier schafft:

Zitat:

Original von HAL 9000
Wenn du z.B. zeigen könntest, dass man damit alle Transpositionen konstruieren kann...

02.01.2023, 13:31

Weduschij

Auf diesen Beitrag antworten »

Okay vielleicht hab ich was.

(k,k+1) * (1,2,3,...,n) = (k,k+2)
(k,k+2)*(1,2,3,...n) = (k+1,k+3) |Kann man fortführen bis man (n,2) enthält.
Dann (k,k+1) *(1,2,3,...n)*(1,2,3,...n)= (k,k+3)

Jetzt muss ich hieraus eine allgemeine Formel entwickeln, oder?

(k,k+1) * (1,2,3,....,n)^x = (k,k+1+x) für x aus N

und

(k,k+1+x) *(1,2,3,...n) =(k+1,k+2+x)

Hiermit kann man jegliche Transposition erzeugen, also kann man auch jede Permutation erzeugen, richtig?

02.01.2023, 13:46

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Weduschij
(k,k+1) * (1,2,3,...,n) = (k,k+2)

Da bekomme ich aber was anderes heraus. unglücklich

Ich hatte an sowas gedacht:

$\begin{eqnarray*} (1~k) \circ (k~k\!+\!1)\circ (1~k) = (1~k\!+\!1) \end{eqnarray*}$ liefert sukzessive alle Transpositionen $\begin{eqnarray*} (1~k) \end{eqnarray*}$ ; und darauf aufbauend über $\begin{eqnarray*} (1~k) \circ (1~l)\circ (1~k) = (k~l) \end{eqnarray*}$ für $\begin{eqnarray*} k\neq l \end{eqnarray*}$ dann schließlich auch alle Transpositionen.

02.01.2023, 13:53

Weduschij

Auf diesen Beitrag antworten »

Hab meinen Fehler erkannt typischer Denkfehler.

02.01.2023, 13:57

Weduschij

Auf diesen Beitrag antworten »

Aber ich dachte wir dürfen nur benachbarte Transpositionen nutzen. Diese Bedingung erfüllt ( 1 k) doch nicht zwingend.

02.01.2023, 13:59

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
$\begin{eqnarray*} (1~k) \circ (k~k\!+\!1)\circ (1~k) = (1~k\!+\!1) \end{eqnarray*}$ liefert sukzessive alle Transpositionen $\begin{eqnarray*} (1~k) \end{eqnarray*}$ ;

Hinter diesem einem Wörtchen versteckt sich quasi der Induktionsschritt $\begin{eqnarray*} k\to k+1 \end{eqnarray*}$ einer Vollständigen Induktion: Induktionsanfang $\begin{eqnarray*} k=2 \end{eqnarray*}$ ist per Voraussetzung ja erfüllt.

02.01.2023, 14:12

Weduschij

Auf diesen Beitrag antworten »

okay das habe ich verstanden. Jetzt habe ich ja bewiesen, dass ich jegliche Transposition erzeugen kann, dennoch mit Hilfe des Hinweises. Beim Hinweis wird ja dennoch mit der "umgekehrten Permutation" gearbeitet. Was ich nicht ganz verstehe ist, wie ich diese umgekehrte Permutation aus s_n erzeugen kann.

02.01.2023, 15:10

HAL 9000

Auf diesen Beitrag antworten »

Ich weiß jetzt nicht genau, was du meinst: Im Hinweis ist von $\begin{eqnarray*} (1~2~\ldots~n)^{-1} \end{eqnarray*}$ die Rede, was man als $\begin{eqnarray*} (n~\ldots~2~1) \end{eqnarray*}$ schreiben kann oder auch (wie du oben) als $\begin{eqnarray*} (1~n~\ldots~3~2) \end{eqnarray*}$ .

Aber worauf willst du hinaus, das hier nochmal zu erwähnen? Wir haben nun alle Transpositionen, damit alle Zykel, und damit dann auch alle Permutationen durch entsprechendes Zusammensetzen aus den beiden Basispermutationen $\begin{eqnarray*} (1~2) \end{eqnarray*}$ sowie $\begin{eqnarray*} (1~2~\ldots~n) \end{eqnarray*}$ bauen können - was willst du da noch mehr? verwirrt

02.01.2023, 15:24

Weduschij

Auf diesen Beitrag antworten »

Alles gut, hat sich erledigt. Vielen vielen Dank nochmals

Neue Frage »

Antworten »

Permutationen erzeugen

Verwandte Themen