a) Sie muss injektiv sein
b) Sie muss strukturerhaltend sein
c) Sie muss surjektiv sein
d) Sie muss Abstände erhalten
Bitte die richtige Zahl eintragen!
Sei M = { 0,2,4,6,8 }. Die folgenden Mengen sollen der Mächtigkeit nach sortiert werden:
a) Die Potenzmenge von M
b) Das kartesische Produkt M × M × M
c) Die Menge aller Permutationen von M
Bitte die Menge mit den meißten Elementen zuerst angeben (beispielsweise hinter 1. den Buchstaben a eintragen)!
Zum Üben: Sei f = ( 1 7 2 ) ( 3 4 ) eine Permutation auf {1,2,3,4,5,6,7,8}. Was stimmt?
a) f ( 7 ) = 2 b) f ( 4 ) = 3 c) f ( f ( 1 ) ) = 2 d) f ( 5 ) = f (8 )
a) f g besitzt einen Fixpunkt 4 ( D. h. es ist ( f g ) (4) = 4 )
b) f g ist ein Zykel der Länge 4 ( D. h. es ist ( f g ) = ( w x y z ) )
c) f g ist eine gerade Permutation
d) f g =  g f
Jede Permutation kann als Verkettung von Transpositionen aufgeschrieben werden
Wenn f eine Permutation ist, für die (1 3 ) f ( 1 2 ) = id gilt,
dann kann f keine Transposition sein
h = ( 1 3 5 ) ( 1 3 ) ( 3 1 5 ) ( 1 4 )
soll einfacher aufgeschrieben werden. Was ist richtig?
a) h = ( 1 4 ) ( 3 5 ) b) h = ( 1 3 ) ( 1 4 ) c) h = ( 1 4 ) ( 1 3 ) d) h = ( 4 1 ) ( 3 5 )
Zur Permutation f = ( a1 a2 ... an ) ist die Permutation g = ( an an-1 ... a1 ) invers
Eine gerade Permutation kann bekanntlich durch eine gerade Anzahl an Transpositionen dargestellt werden. Wir interessieren uns in dieser Frage für die Anzahl N aller geraden Permutationen einer n - elementigen Menge. Damit es einfacher wird, sei n > 1 vorausgesetzt.
a ) N ist für jede natürliche Zahl n eine gerade Zahl
b) N ist genau dann gerade, wenn n gerade ist
c) N ist genau dann gerade, wenn n eine Zweierpotenz ist
d) Keine der Behauptungen a), b) oder c) ist richtig
Die Zykelschreibweise soll hier nur an einem Beispiel erklärt werden:
Sei f : {1,2,3,4,5,6} → {1,2,3,4,5,6} folgende Permutation:
f ( 1 ) = 4, f ( 2 ) = 1, f ( 3 ) = 6, f ( 4 ) = 2, f( 5 ) = 5, f ( 6 ) = 3
Dann lautet f in Zykelschreibweise f = ( 1 4 2 ) ( 3 6 )
Also : Man notiert ein Element, welches nicht auf sich selbst abgebildet wird ( hier die 1 ), schreibt danach das Bild dieses Elements auf ( im Beispiel 4 ), danach das Bild dieses Elements , bis irgendwann das zuerst aufgeschriebene Element dieses Zykels als Bild vorkommt ( im Beispiel f ( 2 ) = 1, dies war der Startwert in diesem Zykel). Gibt es weitere Elemente, die nicht auf sich abgebildet werden und noch nicht aufgeschrieben wurden, geht das Spiel von vorne los. Elemente, die unter der Abbildung Fixpunkte sind, werden einfach weggelassen!
Zurück zum Start
Der Rest ist mehr oder weniger unsinnig, denn für beliebige Mengen muss weder eine weitere Struktur (wie bei Gruppen) noch ein Abstandsbegriff erklärt sein. Damit haben Permutationen nichts zu tun!
Urbild: 1 2 3 4 5 6 7 8 zugehöriges Bild: 7 1 4 3 5 6 2 8
Damit sind a) und b) sofort als korrekt einzusehen.
Zu c): f ( f ( 1 ) ) = f ( 7 ) = 2 , also auch richtig.
Zu d): f ( 5 ) = f ( 8 ) kann überhaupt nicht stimmen, denn f ist bijektiv!
:
Diese Zahl ist 4! = 24
Es ist also h = (1 4 ) ( 3 5 ) = ( 4 1 ) ( 3 5 ) , damit sind a) und d ) richtig.
b) ( 1 3 ) ( 1 4 ) und c) ( 1 4 ) ( 1 3 ) sind falsch, in beiden Fällen wird der 5 nicht das richtige Bild 3 zugeordnet.
Für n = 1 gibt es nur die (gerade) Identität. Für n > 1 gibt es genauso viele gerade wie ungerade Permutationen, nämlich N = n! / 2
Damit ist N für alle natürlichen Zahlen n > 3 gerade, aber nicht für n = 2 und n = 3. Also sind a), b) und c) alle falsch und d) war anzukreuzen.
a) die Potenzmenge von M aus 2n Elementen, wegen M = { 0,2,4,6,8 } also 25 = 32
b) das kartesische Produkt M × M × M aus n3 Elementen, also 53 = 125
c) die Menge aller Permutationen von M aus n! Elementen, also 5! = 120
Damit ist die richtige Reihenfolge b - c - a .
Wenn f eine Transposition wäre, wäre die identische Abbildung wegen ( 1 3 ) f ( 1 2 ) = id eine ungerade Permutation, dies ist aber falsch.
oder : Aus ( 1 3 ) f ( 1 2 ) = id folgt f = ( 1 3 ) ( 1 2 ) = (1 2 3 )
(Beachte: ( 1 3 ) und ( 1 2 ) sind selbstinvers), und damit ist f keine Transposition.
( f Transposition bedeutet : f ist darstellbar als ein Zweierzykel)
f = ( a1 a2 a3 ... an ) = ( a1 a2 ) ( a2 a3 ) ... ( an-1 an )
(Man führe die Verkettung der Transpositionen von rechts nach links durch!)
f g = ( 1 3 4 ) ( 1 2 ) ( 3 4 ) = ( 1 2 3 ) = ( 1 2 ) ( 2 3 ) und g f = ( 1 4 2 ). Also:
a) f g besitzt einen Fixpunkt 4 ist richtig
b) f g ist ein Zykel der Länge 4 ist falsch ( f g ist ein Zykel der Länge 3)
c) f g ist eine gerade Permutation ist richtig ( f g besteht aus zwei Transpositionen)
d) f g = g f ist falsch.
g = ( an an-1 ... a1 ) = ( an an-1 ) ( an-1 an-2 ) ... ( a2 a1 ) = ( an-1 an ) ( an-2 an-1 ) ... ( a1 a2 )
Unter Beachtung der Tatsache, dass jede Transposition selbstinvers ist, folgt die Behauptung f g = id durch intensives Hingucken oder durch eifriges Rechnen.