Bestimmung der Ordnung der Permutation ( 5 1 4 9 7 3 2 8 6 0 ) aus den Zykeln

Question

Es sei \( \pi \) eine Permutation und \( \pi^k \) wie in der Aufgabe 2 definiert. Die kleinste natürliche Zahl \( k \geq 1 \), für die \( \pi^k = id \) ist, nennen wir Ordnung der Permutation \( \pi \). (Dabei ist \( id \) die identische Permutation - für diese gilt \( id(x) = x \) für jedes x.

a) Bestimmen Sie die Ordnung der Permutation (5149732860).

b) Wie kann man die Ordnung aus den Zykeln bestimmen?

Comments

Vom Duplikat:

Titel: Permutation und Aquivalenzrelation

Stichworte: permutation,äquivalenzrelation,zyklen,ordnung

Die Permutation lautet

π:X→X

Mit
π^k
wird die Permutation bezeichnet die k-fach angewandt wurde

genauer:
π^1=π
und
π^k=π∘π^{k−1}

a) Beweisen sie, dass diese Permutation eine Aquivalenzrelation ist.

b) Geben sie die Aquivalenzklassen an

c) Bestimmen sie die ordnung der Permutation (5 1 4 9 7 3 2 8 6 0)

d) Wie kann man die Permutation aus Zyklen bestimmen

zu a habe ich dass

π^k(i1)=j1=j2=..=jn  , π^k(i1)=j1

π^k(i1)=j2 , π^k(i2)=j1

π^k(i1)=jn , π^k(in)=j1

reflexiv, denn i kann j sein ( i = j )  also  i R j  => reflexiv

symmetrisch, denn π(i1)=j2 , i1 R j2 , π(i2)=j1 i2 R j1 ,( i1=j1, i2=j2)  => symmetrisch

transitiv, denn π(i1)=j1 , π(i1)=j2   (j2=i3) -> π(i3)=j1 => transitiv

Aquivalenzklassen kann ich nicht bilden :(

zu c)   (0 1 2 3 4 5 6 7 8 9 )

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

zu d)

1->1,  5->3->8->0 , 4->7->8->6->2

Kann mir jemand sagen ob das richtig ist bzw. berichtigen und tipp gegen?

Answer 1

Die Permutation

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

ist in der Tupelschreibweise gegeben. Diese Schreibweise verwendet nur die zweite Zeile der Zweizeilenschreibweise, in der diese Permutation so aussähe:

0 1 2 3 4 5 6 7 8 9
5 1 4 9 7 3 2 8 6 0

a) Die Ordnung einer Permutation kann man ermitteln, indem man die Permutation wiederholt hintereinander ausführt, bis sich die identische Permutation ergibt. Die Anzahl der dazu erforderlichen Hintereinanderausführungen der Permutation ist deren Ordnung.

Bei der vorliegenden Permutation sieht das so aus:

0 1 2 3 4 5 6 7 8 9  -> π⁰
5 1 4 9 7 3 2 8 6 0 
3 1 7 0 8 9 4 6 2 5
9 1 8 5 6 0 7 2 4 3
0 1 6 3 2 5 8 4 7 9
5 1 2 9 4 3 6 7 8 0 -> π⁵
3 1 4 0 7 9 2 8 6 5
9 1 7 5 8 0 4 6 2 3
0 1 8 3 6 5 7 2 4 9
5 1 6 9 2 3 8 4 7 0
3 1 2 0 4 9 6 7 8 5 -> π¹⁰
9 1 4 5 7 0 2 8 6 3
0 1 7 3 8 5 4 6 2 9
5 1 8 9 6 3 7 2 4 0
3 1 6 0 2 9 8 4 7 5
9 1 2 5 4 0 6 7 8 3 -> π¹⁵ 
0 1 4 3 7 5 2 8 6 9
5 1 7 9 8 3 4 6 2 0
3 1 8 0 6 9 7 2 4 5
9 1 6 5 2 0 8 4 7 3
0 1 2 3 4 5 6 7 8 9 -> π²⁰

Für k = 20 ist π^k erstmalig wieder gleich π⁰  . Also ist k = 20 die Ordnung der Permutation.

 

b) Schreibt man die Permutation in Zykelschreibweise, so erhält man:

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

Zykel der Längen 1 können weggelassen werden, dann ergibt sich:

( 0 5 3 9 ) ( 2 4 7 8 6 )

Die Ordnung k der Permutation ergibt sich daraus als kgV der Längen aller Zykel, vorliegend also:

k = kgV ( 4 , 5 ) = 20