Wir wollen uns mit Permuationen beschäftigen, also mit Bijektionen einer endlichen Menge M auf sich. Einerseits soll grundlegendes Wissen über Permutationen wiederholt werden, andererseits soll das vielleicht ungewohnte Rechnen mit Hilfe der praktischen  Zykelschreibweise  geübt werden. Es wird ferner vorausgesetzt, dass die Begriffe  Transposition  und  gerade Permutation  bekannt sind.
 
Frage 1:

Welche der folgenden Eigenschaften muss eine Permutation besitzen?

     a)   Sie muss injektiv sein

     b)   Sie muss strukturerhaltend sein

     c)   Sie muss surjektiv sein

     d)   Sie muss Abstände erhalten
 

  Ankreuzen:      a)       b)       c)       d) 
    Zur Kontrolle              oder          zur nächsten Frage

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 



 
Frage 2:
Wieviele Permutationen von  {1,2,3,4,5} gibt es, die 4 auf   2 abbilden?

Bitte die richtige Zahl eintragen!

 

  Erst die Zahl eintippen: 
  Zur Kontrolle             oder          zur nächsten Frage

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 



 
Frage 3:
Eine Frage zur Wiederholung von anderen Begriffen:

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)!

  Erst  Eintragen:      Die Reihenfolge ist  1.   2.     3. 
  Zur Kontrolle             oder          zur nächsten Frage

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 



 
 
Frage 4:

Ab jetzt benutzen wir die Zykelschreibweise.

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 )
 

 Erst  Kreuzchen machen:      a)      b)     c)     d) 
  Zur Kontrolle             oder          zur nächsten Frage

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 



 
 
Frage 5:
 Sei in Zykelschreibweise   f = ( 1 3 4 )  und   g = ( 1 2 )( 3 4 ).  Was stimmt für die verkettete Abbildung   f g ?

   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
 

Erst die Kreuzchen machen:     a)      b)      c)      d) 
  Zur Kontrolle             oder          zur nächsten Frage

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 



 
Frage 6:

 Wahr  oder  falsch?

  Jede Permutation kann als Verkettung von Transpositionen aufgeschrieben werden

 

Erst das Kreuzchen machen:      Wahr      Falsch 
  Zur Kontrolle             oder          zur nächsten Frage

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 



 
Frage 7:

 Wahr  oder  falsch?

Wenn   eine Permutation ist, für die   (1 3 ) f ( 1 2 ) =  id   gilt,

dann kann  f   keine Transposition sein

 

Erst das Kreuzchen machen:      Wahr       Falsch 
Zur Kontrolle             oder          zur nächsten Frage

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 



 
Frage 8:

Die folgende Verkettung von Permutationen

 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)   =  ( 1 3 ) ( 1 4 )
   c)   h  =  ( 1 4 ) ( 1 3 )
   d)   h  =  ( 4 1 ) ( 3 5 )
 

  Erst die Kreuzchen machen:      a)       b)       c)       d) 
  Zur Kontrolle             oder          zur nächsten Frage

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 



 
Frage 9:

Wahr  oder  falsch?

Zur Permutation  f  = ( a1 a2 ... an )  ist die Permutation  g = ( an an-1 ... a1 )  invers

 

Erst ein Kreuzchen machen:      Wahr      Falsch 
Zur Kontrolle             oder          zur letzten Frage

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 



 
Frage 10:
 Gleich ist es geschafft! Was stimmt? 

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  eine gerade Zahl

 b)   ist genau dann gerade, wenn n  gerade ist

 c)   ist genau dann gerade, wenn n  eine  Zweierpotenz  ist

 d)  Keine der Behauptungen a), b) oder c) ist richtig
 

  Erst  Kreuzchen machen:      a)       b)     c)       d) 
Zur Kontrolle             oder          zur Auswertung

 
 
 
 
 
 
 
 
 
 


    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
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 



 
 
Antwort zur Frage 1  Richtig anzukreuzen sind   a)  und   c):

Permutationen  ind bijektive Abbildungen einer endlichen Menge   M  auf sich, und  bijektiv  bedeutet  injektiv  und  surjektiv .  Damit sind bei  a)  und   c)  Kreuze notwendig.

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!
 

zurück zur Frage            oder         zur nächsten Frage

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 



 
 
Antwort zur Frage 4:        a), b)  und  c)  sind richtig:
 Für   f = ( 1 7 2 ) ( 3 4 ) gilt  nach Definition

               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!
 

zurück zur Frage     oder   zur nächsten Frage

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 


:
 
 
 

Antwort zur Frage 2           Die gesuchte Zahl ist   24:

Da ein Paar   Urbild - Bild  vorgegeben ist, geht es um die Anzahl aller Bijektionen zwischen den vier – elementigen Mengen  {1,2,3,5}  und   {1,3,4,5}.

Diese Zahl ist 4! = 24
 

zurück zur Frage             zur nächsten Frage

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 



 
 
Antwort zur Frage 8    a) und d) waren anzukreuzen:
Für  h = ( 1 3 5 ) ( 1 3 ) ( 3 1 5 ) ( 1 4 )  gilt, wenn wir die einzelnen Zykel  von rechts nach links abarbeiten:

 
Urbild :    1    2    3    4    5
zugehöriges Bild unter ( 1 4 ) :    4    2    3    1    5
zugehöriges Bild unter ( 3 1 5 ) :    4    2    1    5    3
zugehöriges Bild unter ( 1 3 ) :    4    2    3    5    1
zugehöriges Bild unter ( 1 3 5) :    4    2    5    1    3

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. 

zurück zur Frage       zur nächsten Frage

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 



 
 
Antwort zur Frage 10     Kreuz bei d):

Die Anzahl aller Permutationen einer   n - elementigen Menge ist bekanntlich  n!

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  Nn! / 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.
 

zurück zur Frage        zur Auswertung

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 



 
 
Antwort zur Frage 3:   Die Reihenfolge ist b), c), a): 
Bei einer  n - elementigen Menge  M  besteht

  a)  die Potenzmenge von  aus  2n   Elementen, wegen  M = { 0,2,4,6,8 } also  25 =  32

  b)  das kartesische Produkt  M × M × M   aus   nElementen,  also  53  =  125

  c)  die Menge aller Permutationen von   M   aus  n!  Elementen,  also  5! =  120

 
 Damit ist die richtige Reihenfolge  b - c - a .
 

zurück zur Frage          zur nächsten Frage

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 



 
 
Antwort zur Frage 7:          Wahr:
Dass  f  keine Transposition sein kann, kann man auf verschiedene Weisen einsehen:

Wenn  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)

zurück zur Frage      zur nächsten Frage

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 



 
Antwort zur Frage 6:       Kreuz bei Wahr:
Jede Permutation kann als Verkettung von Transpositionen aufgeschrieben werden, hierzu ein Beweisfragment:

 f  = ( a1 a2 a... an ) =  ( a1 a2 ) ( a2 a3 ) ...  ( an-1  an )

(Man führe die Verkettung der Transpositionen von  rechts  nach  links  durch!)
 

zurück zur Frage         zur nächsten Frage

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 



 
 
Antwort zur Frage 5:         Kreuze bei a) und c):
  Für  f = ( 1 3 4 )  und  g = ( 1 2 )( 3 4 )  folgt durch einfache Rechnung 

  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.
 

zurück zur Frage         zur nächsten Frage

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 



 
 
Antwort zur Frage 9:        Kreuz bei wahr:

Zu  f  = ( a1 a2 ... an )  ist die Permutation  g =  ( an an-1 ... a1 )  invers, denn es ist (siehe Frage 6)

    f  = ( a1 a2 a3 ... an ) =  ( a1 a2 ) ( a2 a3 )  ...  ( an-1  an

   g = ( an  an-1 ... a1 ) =   ( an  an-1 ) ( an-1 an-2 ) ... ( a a)  =  ( an- an ) ( an-2 an-1 ) ... ( a a2 )

Unter Beachtung der Tatsache, dass jede Transposition selbstinvers ist, folgt die Behauptung
 f g  =  id  durch intensives Hingucken oder durch eifriges Rechnen. 
 

zurück zur Frage                  zur nächsten Frage

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 





 
 
Erzielt  Punkte von maximal 
Umgerechnet  Prozent
Dies ist 
-----
Benötigte Zeit  Sekunden
Damit werden Prozent angerechnet
Damit ist die Leistung insgesamt

 

zurück zur ersten Frage        zum Fragenkatalog

 
 
 
 
 
 



H J Samaga, 18.04.01 / 10.07.01 / 19.05.05