Signum

Neue Frage »

energyfull Auf diesen Beitrag antworten »
Signum
halla ich habe nicht verstanden, wie man das signum einer permutation berechnet, kann mir das einer anhand dieses beispiels erklären:



wie muss ich hier vorgehen, was muss zuerst gemacht werden???
Mazze Auf diesen Beitrag antworten »

Eine Möglichkeit das Signum zu berechnen ist die Anzahl der Fehlstände zu bestimmen. Ein Fehlstand ist ein Paar (i,j) mit und . Ist die Anzahl der Fehlstände gerade ist das Signum +1 ansonsten -1. Beispiel :

1 2 3 4 5

Fehlstände 0

Signum +1

1 2 3 5 4

Fehlstände 1

i = 4, j = 5

Signum -1

1 3 2 5 4

Fehlstände 2

i = 2, j = 3 ; i = 4, j = 5

Signum +1

Ansonsten kann man auch die Anzahl der Transpositionen zählen, also die Anzahl der Transpositionen, die benötigt werden um eine gegebene Permutation aus der Identischen Permutation zu erhalten. Hierbei ist wieder das Signum + 1 wenn die Anzahl gerade ist und -1 sonst.
energyfull Auf diesen Beitrag antworten »

ok so weit habe ich das jetzt verstanden,

wenn ich die permutation von diesem beispiel berechnen will, muss ich doch auch die vollständige induktion anwenden, das ist mir aber noch nicht klar wie ich das mache.
Mazze Auf diesen Beitrag antworten »

Zitat:
wenn ich die permutation von diesem beispiel berechnen will, muss ich doch auch die vollständige induktion anwenden, das ist mir aber noch nicht klar wie ich das mache.


Nö musst Du nicht, die Anzahl der Fehlstände von



ist sehr sehr sehr klein (nicht 0 aber sehr klein). Und das völlig unabhängig von der Größe von n. Vollständige Induktion braucht man hier nicht. Ginge aber auch mit vollständiger Induktion.
energyfull Auf diesen Beitrag antworten »

kannst du mir erklären wie ich das mit induktion mache
Mazze Auf diesen Beitrag antworten »

Ich würde hier völlig auf Induktion verzichten. Es gibt genau einen Fehlstand i = n - 1 und j = ?.
 
 
AD Auf diesen Beitrag antworten »

Zitat:
Original von Mazze
Es gibt genau einen Fehlstand i = n - 1 und j = ?.

Meinst du das so, dass es genau einen Fehlstand (i,j) mit i=n-1 gibt? verwirrt

Denn ansonsten gibst es bei der Permutation ja genau (n-1) Fehlstände, gemäß üblicher Definition eines Permutationsfehlstandes.
energyfull Auf diesen Beitrag antworten »

i=n-1


ist dann j= n

ich bin ein bisschen verwirrt
Mazze Auf diesen Beitrag antworten »

Zitat:
Meinst du das so, dass es genau einen Fehlstand (i,j) mit i=n-1 gibt? verwirrt Denn ansonsten gibst es bei der Permutation ja genau (n-1) Fehlstände, gemäß üblicher Definition eines Permutationsfehlstandes.


Ich bin gerade fast auf dem Bett eingeschlafen, habe kurz drüber nachgedacht und bin aufgeschreckt. Du hast recht mit n - 1 Fehlständen.

Zitat:
i=n-1 ist dann j= n ich bin ein bisschen verwirrt


Ja, das ist ein Fehlstand. Natürlich gibt es n - 1 Fehlstände da die 1 am ende ist. Lässt sich aber auch ohne Induktion zeigen.

Beispiel :

2 3 4 5 1

Fehlstände

(Indizes)
(1,5),(2,5),(3,5),(4,5)
energyfull Auf diesen Beitrag antworten »

hmm wie kann ich jetzt das sigmum berechnen bzw.angeben
Mazze Auf diesen Beitrag antworten »

Hab ich doch oben schon gesagt, das Signum ist +1 wenn die Anzahl der Fehlstände gerade ist und -1 sonst. Wenn Du es wirklich mit Induktion machen willst beweise die Aussage :

energyfull Auf diesen Beitrag antworten »

also ist das sigmum hier -1

oki,


ich will es auch gerne mit induktion versuchen, weiss aber nicht wirklich wie diese aussage beweisen kann
energyfull Auf diesen Beitrag antworten »

stimmt es denn das das signum -1 ist
Mazze Auf diesen Beitrag antworten »

Zitat:
ich will es auch gerne mit induktion versuchen, weiss aber nicht wirklich wie diese aussage beweisen kann


Induktionsanfang für n = 1

Die Permutation 1 hat genau 0 Fehlstände. Das heisst das Signum ist +1. Mit gilt also die Aussage.#


Induktionsschritt :

Zeige nun das gilt mit Hilfe der Induktionsvoraussetzung (wie gewöhnlich).
energyfull Auf diesen Beitrag antworten »

danke dir für deine antwort und hilfe,

ich soll ja wie gewöhlich mit induktionsschritt weiter machen, aber wie geht das hier
Mazze Auf diesen Beitrag antworten »

Überleg Dir einfach mal wieviel mehr Fehlstände Du erzeugst, wenn Du n um eins erhöhst.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »