Permutationen, Tupel-, Zyklen-Schreibweise, Zweizeilenform
- Autor:
- hawe
- Thema:
- Mathematik, Matrizen, Folgen und Reihen
Ich stelle einige CAS-Funktionen bereit um damit Permutationen darzustellen, zu verketten und zu untersuchen.
Permutationen
Zyklische Permutationen
Erzeugen eines Index Tupels mit n Einträgen So(n)
S_4:=S_o(4)
Eine Permutation
π: {1,2,3,4} -> {2,4,3,1} \ (π(1)=2,π(2)=4,π(3)=3,π(4)=1}
in Zweizeilenform
π_1:={S_o(4),{2,4,3,1}}
in Tupelform ohne die 1. Zeile, Zuordnung durch den Index der Liste
Tupel werden als Liste {...} geführt, die anderen Formen als Matrix {{...},...{...}} - Funktionenargumente sind Listen: ggf. Flatten(Matrix) in Liste überführen!
und als Zykel (zyklische Darstellung: beginn bei 1, länge 3: 1 -> 2 -> 4 ->1, 3 fix wird nicht aufgeschrieben)
π_3:PknZykel(π_2, 1, 3)
In der Zyklenschreibweise erhält man die inverse Permutation, indem man in jedem Zyklus die Zahlen in der umgekehrten Reihenfolge schreibt.
Zykel in Tupel (Argument in Listenform - flatten(matrix))
Zykel(Flatten(π_3),4)
Zerlegung einer Permutation in Zykelschreibweise PknZykel() als Produkt disjunkter (elementfremder) Zykel:
1. Zyklus bestimmen beginne bei 1- suche über ganze Länge 5
PknZykel(S5_i, 1, 5)
1. Zyklus bei 1,Länge 2, suche bei 2, max. Länge 3 (5 - 2 gefunden)
PknZykel(S5_i, 2, 3)
Zusammenfassung Zweizeilenform, elementfremde Zykel mit Signum der Permutation
Zykel-Ketten immer von rechts nach links abarbeiten!
{{S_o(5), S5_i}, PknZykel(S5_i, 1, 2), PknZykel(S5_i, 2, 3), pSgn(S5_i)}
Verkettung (hintereinander ausführen) von Permutationen, wandle die für S5_i gefundenen Zykel in Tupel:
z5_i:{Zykel({1,3},5), Zykel({2,4,5},5)}
Verketten Funktionen pop() ∨ PChain(z5i,8): führe zuerst {2,4,5} und dann {1,3} aus
pop(Element(z5_i,1), Element(z5_i,2))
=S5_i - die Ausführung der zyklischen Vertauschungen ergibt wieder das Ausgangstupel
---
σ3:{{1, 2, 3} ,{1,3,2}, {2,1,3}, {3,2,1}, {2,3,1}, {3,1,2}}
σ3(6) ° σ3(2) -> PChain({Element(σ3,6),Element(σ3,2)},3) -> {3, 2, 1}
Potenzen einer Permutation (Tupel σ n)
σ:{6,8,2,7,5,1,3,4}
σ'^n = IterationList[pop(a, σ), a, {σ}, n-1]
Transpositionen, Permutationen, die genau zwei Objekte vertauschen:
Schreibe p_i als Produkt von Transpositionen (beispielhaft in Zykel ∧ Tupel-Schreibweise)
{1,2,3,4} Tausche 1<> 4
t_{14}:=Zykel({1,4},4)
dann Tausche 2 <> 4
t_{24}:=Zykel({2,4},4)
pop(t_{24), t_{1,4))
{2,4,3,1} = {2,4}2{1,4}1 Transpositions-Kette
Allgemein ausgehend von Zykelschreibweise:
Beispiel:
Tupelσ_1:={S_o(7), {6,3,1,4,5,7,2}}
Zykelσ_1:{PknZykel(Element(Tupelσ_1,2), 1, 5)}
Transpoσ1:{{{1,3}},{{1,2}},{{1,7}},{{1,6}}}
TT:=Sequence(Zykel(Element(Transpoσ1, j, 1), 7), j, 1, Length(Transpoσ1))
PChain(TT, 7)
Beispiele und Kopiervorlagen für User-Functions Permutation
Lesen Permutation Tupel, Zykel
Pα Pβ Pα^-1
Create Permutations
Wenn man nun zeigen kann, dass man alle Transpositionen als Produktevon Elementen aus MMM schreiben kann, ist der Beweis erbracht. Man rechnet leicht nach, dass
Hieraus ergibt sich:
so dass sich(1,3)(1,3)(1,3) als Produkt der Elemente von MMM schreiben lässt.
So verfahren wir weiter:
Entsprechend erhalten wir alle Transpositionen der Gestalt (1,k)(1,k)(1,k) als Produkt der MMM-Elemente.Eine beliebige Transpostion (j,k)(j,k)(j,k) können wir schreiben als
Alle Transpositionen sind also als Produkte der Elemente aus MMM schreibbar,
Fixpunkte
, Rekusiv
pn_k(n):=n! Sum((-1)^k/k!,k,0,n)
I(XX,kk):=Element(XX, kk)
FixPunktfreiP_6:=IterationList({I(X, 1)+1,(I(X, 1)+1) I(X, 2)+ (-1)^(I(X, 1)+1)},X, {{0,1}}, 6)
Anzahl Permutationen Pn mit k Fixpunkten
Anzahl aller Permutationen mit genau 1 Fixpunkt (= Anzahl aller Möglichkeiten zur Wahl des Fixpunktes = nCr(n,k) mal Anzahl aller fixpunktfreien Permutationen der restlichen n − k Elemente
Anzahl der Permutationen mit genau x Fixpunkten:
Fixn_k(n,x):=nCr(n,x) pn_k(n-x)
Anzahl P6 mit 2 Fixpunkten
Fixn_k(6,2)=135
Sei Fixnk(k) die Anzahl der Permutationen mit genau k Fixpunkten.
Sum(j Fixn_k(6,j),j,0,6) == 6!
https://www.mathe-gut-erklaert.de/pdfs/000_Fixpunkte_Perm.pdf