[Diskrete] Signum einer Permutation

[GooGooDolls&Lifehouse]

Hey Leute,

Kann mir vielleicht jmd erklaeren, wie ich das Signum einer Permutation berechnen kann, so wie es auf Aufgabenblatt 4 in Aufgabe 1 gefordert wurde?

Den Weg mit der Anzahl der Transposition ist fuer mich nicht nachvollziehbar, da es doch mehrere Moeglichkeiten gibt,eine Permutation durch verschiedene Transpositionen darzustellen oder ist gewaehrleistet, dass die Anzahl dabei immer gleich ist?

Der Loesungsweg mit der Berechnung der Anzahl der Fehlstandspaare waere mir lieber, nur schein ich bei der Berechnung dieser immer Fehler zu machen!?

Vielleicht kann ja jmd eines der Bsp von dem Uebungsblatt ausfuehrlich beschreiben! Des waer voll Titte
muchaaass

[rootnode]

Zerleg das Ding in Zykel.
Nun zähle die Anzahl an geraden Zykeln. Nennen wir diese Anzahl n

Das Signum ist nun:

[Cornflake]

Also korrekter wäre es eigentlich es so auszudrücken:

Hört sich auf den ersten Blick vllt. komplizierter an ist aber richtiger, da das von rootnode nur bei einer Permutation mit gerader Anzahl an Elementen funktioniert.

[rootnode]

Nö, funzt eigentlich immer.
Wenn du jetz beide Reihen mit der Anzahl meintest...dann zeig mir ma ne Permutation wo diese Anzahl ungerade ist.

[kb]

Der Loesungsweg mit der Berechnung der Anzahl der Fehlstandspaare waere mir lieber, nur schein ich bei der Berechnung dieser immer Fehler zu machen!?

Vielleicht kann ja jmd eines der Bsp von dem Uebungsblatt ausfuehrlich beschreiben!

Vielleicht rechnest du falsch? Im Grunde einfach für jede Ziffer der Permutation: "Wie viele größere Ziffern stehen VOR dieser Ziffer". Die Summe des Ganzen ist dann das für . Musst beachten, dass du dafür die Tupelschreibweisen brauchst!

(edit)Für Lösungshilfe bräuchten wir schon die Aufgabe ^^

Cornflakes Lösung ist auch richtig, von rootnode allerdings auch, weils aufs gleiche hinausläuft:
(Ich nehm jetzt mal Cornflakes Formel) Hat ein Zykel gerade Länge, würde die Potenz um eine ungerade Zahl erhöht. Bei einem ungeraden Zykel um eine gerade Zahl. Da es eine Potenz über -1 ist, können wir die geraden Potenzen "streichen", und eine 1 statt jeder ungeraden Potenzen schreiben (ich beziehe mich natürlich auf die Potenzen, die hinzuaddiert werden). Und das ist genau das gleiche, wie wenn man die Anzahl der geraden Zykeln nimmt ;]
(edit2) Dieser Lösungsweg ist dann für die Zykelschreibweise geeignet. Je nach dem sparst du dir die "Umrechnung".

[Cornflake]

Nö, funzt eigentlich immer.
Wenn du jetz beide Reihen mit der Anzahl meintest...dann zeig mir ma ne Permutation wo diese Anzahl ungerade ist.

Okay, okay, hatte überlesen, dass du geschrieben hattest Anzahl an geraden Zykeln. Wir hatten nämlich das Problem, dass im Übungsblatt die Anzahl der Elemente immer gerade war und wir dann einfach die Anzahl der Zykel gezählt hatten, was dann zwar für das Übungsblatt richtig war aber natürlich irgendwann später Probleme bereitet hatte.
Aber wenn man nur die GERADEN Zykel zählt stimmt es natürlich wieder.

Auch danke an kb, nette Erläuterung.

[GooGooDolls&Lifehouse]

Danke euch!!

@rootnode
Also, es ist wichtig NUR die GRADEN ZYKEL zu zählen,nä? Sonst wirds falsch! Es sei denn die Herren von DS haben die Aufgaben so getüdelt, dass es nicht auffällt. Also ich finde echt, dass die sich mal ein bisschen mehr Mühe hätten geben können!
Wenn man nur die Anzahl Grader Zykel berücksichtigt klappt es nämlich immer, nicht wie in der Globalübung die generelle Anzahl von Zykeln.
Vielen Dank!!!

@kb
Dein Lösungsweg gefällt mir auch gut! Gut zu wissen, dass man das Signum auch aus der Matrix/Tupelansicht ersehen kann!

@cornflake
Du kriegst noch ne Extraantwort

Ich denke ich habs jetzt, ansonsten merkert bitte!!!!!!
Hier mal ein Bsp:

Permutation p:
( 1 2 3 4 5 6 7 8 9
7 9 4 8 3 2 1 5 6 )

Nach kb:
Wieviele größere Ziffern stehen vor:
7 -> 0 (d.h. Vor 7 stehen 0 Ziffern, die grösser sind als 7)
9 -> 0
4 -> 2
8 -> 2
3 -> 3
2 -> 5
1 -> 6
5 -> 3
6 -> 3

Die Summe der Anzahlen:
2+2+3+5+6+3+3 = 24

=> sgn(p) = (-1)^24 = 1

Jetzt nach rootnode:

Dieselbe Permutation p:
( 1 2 3 4 5 6 7 8 9
7 9 4 8 3 2 1 5 6 )

1. In Zykelschreibweise:

(1 7) ° (2 9 6) ° (3 4 8 5)

Länge der Zyklen: 2 3 4.

Anzahl der geraden Zykel: 2.

sgn(p) = (-1)^2 = 1

Irgendwo Fehler?
Nochmal Danke!!

PS:
!!!!!!!! Würde ich die Anzahl aller Zykel -hier 3- nehmen, würde ich ein falsches Ergebnis bekommen, naemlich -1. !!!!!!!!!!!!

[NeX]

wenn überhaupt solltest du auch die länge aller zykel + anzahl zykel nehmen....

2 + 3 + 4 + 3 = 12 .....

( 2+3+4 = 9 = Anzahl aller "Elemente" ....folglich kannst du immer

(-1)^(9+anzahl Zykel) nehmen....)

[GooGooDolls&Lifehouse]

[quote="Cornflake"]Also korrekter wäre es eigentlich es so auszudrücken:
quote]

Mir ist nicht ganz klar was du mit "+ jeweils Länge EINES Zykels" meinst!
Mit eines meinst du jedes einzelen, oder? Bin schon etwas Mathebreit und neige dazu es als irgendeines aufzufassen...lol

Also laut deiner Formel wäre mein Bsp von oben:

Permutation p:
( 1 2 3 4 5 6 7 8 9
7 9 4 8 3 2 1 5 6 )

1. Zykel-Schreibweise:

(1 7) ° (2 9 6) ° (3 4 8 5)

Anzahl Zykel = 3

Länge Zykel 1 = 2.
Länge Zykel 2 = 3.
Länge Zykel 3 = 4.
Summe der Längen = 9

2. Formel:

sgn(p) = (-1)^Anzahl der Zykel + Summe der Länge aller Zykel

sgn(p) = (-1)^12 = 1

Richtig so?

Dank dir!

[kb]

yep, alles richtig =]

[Cornflake]

Anzahl Zykel: 3
Anzahl Elemente: 9
=> (-1)^12

sgn(p) = (-1)^Anzahl der Zykel + Summe der Länge aller Zykel

sgn(p) = (-1)^12 = 1

Richtig so?

Dank dir!

Genau so, also alle Elemente Zählen und alle Zykel zählen und gut is.
Funzt auch auf jeden Fall IMMER.

Aber einfach die Anzahl der geraden Zykel zu zählen is dann doch einfacher, kannte das nur leider vorher nich.