Permutation < Matrizen < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:41 Mi 26.10.2011 | | Autor: | Lunar |
| Aufgabe | | Beweise, dass jede Permutation von (1,2,...,n) eine Komposition von Transpositionen ist. Mit wievielen Transpositionen kommt man aus? |
Hallo zusammen!
Mir ist bei dieser Frage einiges unklar.
Wie beweise ich, dass eine Permutation eine Komposition von Transpositionen ist?
eine Komposition von Transpositionen heisst ja in worten: Ich vertausche 2 Spalten so lange, bis ich die gewünschte permutation habe.
also kann ich zu und dann z.b zu
1 2 3 4 1 2 3 4 1 2 3 4
1 2 3 4 2 1 4 3 2 4 1 3
vertauschen.
aber ich weiss nicht wo mit einem beweis anfangen.
ich versuchte, eine formel zu finden, um es mit induktion zu beweisen, aber da kommt nicht viel schlaues heraus bei mir.
mit wievielen transpositionen kommt man aus? ja das hängt ja von p ab. wenn es für eine permutation nur 1 transposition braucht, muss das ja nicht für alle gelten.
was meint ihr?
|
|
| |
|
moin Lunar,
Die Frage "mit wie vielen kommt man aus" würde gern den worst Case wissen, also mit wie vielen kommt man auf jeden Fall aus, egal wie die Permutation aussieht.
Wenn eine Permutation weniger braucht um so schöner, aber wie viele reichen auf jeden Fall?
Für den Beweis:
Weißt du, was Fehlstände sind?
Kennst du die Zykelschreibweise für Permutationen?
Was kennst du sonst?^^
Mit beiden Dingen, die ich da erwähnt habe, könnte man einen Beweis basteln (nicht notwendigerweise mittels Induktion), aber ich kann dir ja nichts erzählen was du noch nicht hattest.^^
lg
Schadow
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:11 Do 27.10.2011 | | Autor: | Lunar |
Hallo Schadow.
weder Fehlstände noch zykelschreibweise sagte mir etwas. habs jetzt gegoogelt und verstehe nun um was es geht. aber naja, kann damit keinen beweis basteln:D
hat mir jemand noch einen anderen vorschlag für einen beweis?
|
|
|
| |
|
> Hallo Schadow.
>
> weder Fehlstände noch zykelschreibweise sagte mir etwas.
> habs jetzt gegoogelt und verstehe nun um was es geht. aber
> naja, kann damit keinen beweis basteln:D
> hat mir jemand noch einen anderen vorschlag für einen
> beweis?
Moin,
zykelschreibweise ist eine abgekürzte Schreibweise für eine Permutation
[mm]\pi = \pmat{1 & 2 & \ldots &n \\
\pi(1) & \pi (2) & \ldots & \pi(n)}[/mm]
Beispiel
[mm]\pi = \pmat{1 & 2 & 3 & 4 \\
2 & 4 & 1 & 3} = (1243)[/mm]
ich gebe dir mal ein paar Beispiele:
(12) = (12)
(123) = (13)(12)
(1234) = ...
(12345) = ....
Dieses Muster kann man jetzt allgemein für
[mm](a_1,a_2,\ldots,a_n) = (a_1 a_{?})\circ \ldots[/mm]
fortsetzen.
Das wird eventuell doch eine Induktion oder vielmehr ein Verfahren. Ich denke, dass es so intuitiv ist. Dennoch solltest du dich mit den Begriffen auseinandersetzen.
|
|
|
|
