Ich stelle einige CAS-Funktionen bereit um damit Permutationen darzustellen, zu verketten und zu untersuchen. [br][url=https://de.wikipedia.org/wiki/Permutation]Permutationen[/url][math]\nearrow[/math] [br][url=https://de.wikipedia.org/wiki/Zyklische_Permutation]Zyklische Permutationen[/url][math]\nearrow[/math] [br][br][i]Erzeugen eines Index Tupels mit n Einträgen [b]S[sub]o[/sub](n)[/b][/i][br][code]S_4:=S_o(4)[/code][br][math]S_4 \, := \, \left\{ 1, 2, 3, 4 \right\} [/math][br][br][i]Eine Permutation[/i][br]π: {1,2,3,4} -> {2,4,3,1} \ (π(1)=2,π(2)=4,π(3)=3,π(4)=1} [br][br][i]in [color=#ff0000][b]Zweizeilenform [/b][/color][/i][br][math]\left(\begin{array}{rrrr}1&2&3&4\\\pi\left(1 \right)&\pi \left(2 \right)&\pi \left(3 \right)& \pi \left(4 \right)\\\end{array}\right)[/math][br][code]π_1:={S_o(4),{2,4,3,1}}[/code][br][math]\pi_1:=\left(\begin{array}{rrrr}1&2&3&4\\2&4&3&1\\\end{array}\right)[/math][br][br][i]in [color=#ff0000][b]Tupelform [/b][/color]ohne die 1. Zeile, Zuordnung durch den Index der Liste[/i][br][math]\pi_2:= \left\{ 2, 4, 3, 1 \right\} [/math][br][br][color=#cc0000][size=85]Tupel werden als Liste {...} geführt, die anderen Formen als Matrix {{...},...{...}} - Funktionenargumente sind Listen: ggf. Flatten(Matrix) in Liste überführen![/size][/color][br][br][i]und als [color=#ff0000][b]Zykel [/b][/color](zyklische Darstellung: beginn bei 1, länge 3: 1 -> 2 -> 4 ->1, 3 fix wird nicht aufgeschrieben) [/i][br][code]π_3:PknZykel(π_2, 1, 3)[/code][br][math]\pi_3:=\left(\begin{array}{rrr}1&2&4\\\end{array}\right)[/math][br][i]In der Zyklenschreibweise erhält man die inverse Permutation, indem man in jedem Zyklus die Zahlen in der umgekehrten Reihenfolge schreibt.[/i][br][br][i][b][color=#ff0000]Zykel in Tupel [/color][/b] (Argument in Listenform - flatten(matrix))[/i][br][code]Zykel(Flatten(π_3),4)[/code][br][math] \left\{ 2, 4, 3, 1 \right\} [/math][br][br][i]Zerlegung einer Permutation in Zykelschreibweise [b]PknZykel() [/b]als Produkt disjunkter (elementfremder) Zykel:[/i][br][math]S5_i \, := \, \left\{ 3, 4, 1, 5, 2 \right\} [/math][br][i]1. Zyklus bestimmen beginne bei 1- suche über ganze Länge[/i] 5[br][code]PknZykel(S5_i, 1, 5)[/code][br][math]\left(\begin{array}{rrrrr}1&3&1&3&1\\\end{array}\right)[/math] [br][i]1. Zyklus bei 1,Länge 2, suche bei 2, max. Länge 3 [/i](5 - 2 gefunden)[br][code]PknZykel(S5_i, 2, 3)[/code][br][math]\left(\begin{array}{rrrr}2&4&5\\\end{array}\right)[/math][br][br][i]Zusammenfassung Zweizeilenform, elementfremde Zykel mit Signum der Permutation[br]Zykel-Ketten immer von rechts nach links abarbeiten![/i][br][code]{{S_o(5), S5_i}, PknZykel(S5_i, 1, 2), PknZykel(S5_i, 2, 3), pSgn(S5_i)}[/code][br][math] \left\{ \left(\begin{array}{rrrrr}1&2&3&4&5\\3&4&1&5&2\\\end{array}\right), \left(\begin{array}{rr}1&3\\\end{array}\right), \left(\begin{array}{rrr}2&4&5\\\end{array}\right), -1 \right\} [/math][br][br][i]Verkettung (hintereinander ausführen) von Permutationen, wandle die für S5_i gefundenen Zykel in Tupel:[/i][br][code]z5_i:{Zykel({1,3},5), Zykel({2,4,5},5)}[/code][br][math]z5_i \, := \, \left(\begin{array}{rrrrr}3&2&1&4&5\\1&4&3&5&2\\\end{array}\right)[/math][br][br][i][color=#ff0000][b]Verketten [/b][/color][b]Funktionen [/b][b]pop()[/b] ∨ [b]PChain([/b]z5i,8[b])[/b]: führe zuerst {2,4,5} und dann {1,3} aus[/i][br][code]pop(Element(z5_i,1), Element(z5_i,2))[br][/code][br][math] \left\{ 3, 4, 1, 5, 2 \right\} [/math][br][i]=S5_i - die Ausführung der zyklischen Vertauschungen ergibt wieder das Ausgangstupel[br]---[br]σ[sub]3[/sub]:{{1, 2, 3} ,{1,3,2}, {2,1,3}, {3,2,1}, {2,3,1}, {3,1,2}}[br]σ[sub]3[/sub](6) ° σ[sub]3[/sub](2) -> PChain({Element(σ[sub]3[/sub],6),Element(σ[sub]3[/sub],2)},3) -> {3, 2, 1}[br][br][b][color=#ff0000]Potenzen [/color][/b]einer Permutation (Tupel σ[sup] n[/sup])[br]σ:{6,8,2,7,5,1,3,4}[br]σ'^n = IterationList[pop(a, σ), a, {σ}, n-1][br][br][b][color=#ff0000]Transpositionen[/color][/b], Permutationen, die genau zwei Objekte vertauschen:[br]Schreibe p_i als Produkt von Transpositionen (beispielhaft in Zykel ∧ Tupel-Schreibweise)[/i][br][math]p_i:=\left\{ 2, 4, 3, 1 \right\} [/math][br][br][i]{1,2,3,4} Tausche 1<> 4[/i] [br][code]t_{14}:=Zykel({1,4},4)[/code][br][math] \left\{ 4, 2, 3, 1 \right\} [/math][br][i]dann Tausche 2 <> 4[/i] [br][code]t_{24}:=Zykel({2,4},4)[/code][br][math] \left\{ 1, 4, 3, 2 \right\} [/math][br][code]pop(t_{24), t_{1,4))[/code] [br][math] \left\{ 2, 4, 3, 1 \right\} [/math][i][br][br]{2,4,3,1} = [/i]{2,4}[sub]2[/sub]{1,4}[sub]1[/sub] [math]\Leftarrow[/math] [i]Transpositions-Kette[br][br][/i]Allgemein ausgehend von Zykelschreibweise:[br][br][math] \left(a_{1} \ldots a_{k}\right)=\\\left(a_{1} a_{k}\right) \circ\left(a_{1} a_{k-1}\right) \circ \ldots \circ\left(a_{1} a_{2}\right)=\\ \left(\begin{array}{ll}a_{1} & a_{k}\end{array}\right)\left(\begin{array}{ll}a_{1} & a_{k-1}\end{array}\right) \ldots\left(a_{1} a_{2}\right)[br][br][/math][br][br]Beispiel:[br][i]Tupelσ_1:={S_o(7), {6,3,1,4,5,7,2}}[/i][br][math]Tupel\sigma_1 \, := \, \left(\begin{array}{rrrrrrr}1&2&3&4&5&6&7\\6&3&1&4&5&7&2\\\end{array}\right)[/math][br][br][i]Zykelσ_1:{PknZykel(Element(Tupelσ_1,2), 1, 5)}[/i][br][math] \left\{ \left(\begin{array}{rrrrr}1&6&7&2&3\\\end{array}\right) \right\} [/math][br][i][br]Transpoσ1:{{{1,3}},{{1,2}},{{1,7}},{{1,6}}}[/i][br]TT:=Sequence(Zykel(Element(Transpoσ1, j, 1), 7), j, 1, Length(Transpoσ1))[br][math]\left(\begin{array}{rrrrrrr}6&2&3&4&5&1&7\\1&3&2&4&5&6&7\\1&2&6&4&5&3&7\\1&2&3&4&5&7&6\\\end{array}\right)[/math][br][i][br]PChain(TT, 7)[/i][br][math]TupelTT: \left\{ 6, 3, 1, 4, 5, 7, 2 \right\} [/math][br]

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[br][br][math](1,2,⋯ ,k)=\\(1,k)(1,k−1)⋯(1,2)(1,2,\cdots,k)=\\(1,k)(1,k-1)\cdots(1,2)(1,2,⋯,k)=\\(1,k)(1,k−1)⋯(1,2)[/math] [br][br]Hieraus ergibt sich:[br][br][math](1,3)=\\(1,3)(1,2)(1,2)=\\(1,2,3)(1,2)(1,3)=\\(1,3)(1,2)(1,2)=\\(1,2,3)(1,2)(1,3)=\\(1,3)(1,2)(1,2)=\\(1,2,3)(1,2)[/math][br][br]so dass sich(1,3)(1,3)(1,3) als Produkt der Elemente von MMM schreiben lässt. [br]So verfahren wir weiter:[br][br][math](1,2,3,4)(1,2)(1,3)=\\(1,4)(1,3)(1,2)(1,2)(1,3)=\\(1,4)(1,3)(1,3)=\\(1,4)(1,2,3,4)(1,2)(1,3)=\\(1,4)(1,3)(1,2)(1,2)(1,3)=\\(1,4)(1,3)(1,3)=\\(1,4)(1,2,3,4)(1,2)(1,3)=\\(1,4)(1,3)(1,2)(1,2)(1,3)=\\(1,4)(1,3)(1,3)=\\(1,4)[/math][br][br]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 [br][br][math](1,j)(1,k)(1,j)(1,j)(1,k)(1,j)(1,j)(1,k)(1,j)[/math][br][br]Alle Transpositionen sind also als Produkte der Elemente aus MMM schreibbar,

[math]\theta\left(n\right)=\text{Anzahl fixpunktfreier Permutationen von n Elementen}[/math][br][math]\theta\left(n\right)= n! \; \sum_{k=0}^{n}\frac{\left(-1 \right)^{k}}{k!}[/math], Rekusiv [math] a_{n} =\left(n-1\right) \left(a_{n-1}+a_{n-2} \right) [/math][br][br][i]pn_k(n):=n! Sum((-1)^k/k!,k,0,n)[/i][br][br][i]I(XX,kk):=Element(XX, kk)[br]FixPunktfreiP_6:=IterationList({I(X, 1)+1,(I(X, 1)+1) I(X, 2)+ (-1)^(I(X, 1)+1)},X, {{0,1}}, 6)[/i][br][math]\small FixPunktfreiP_6 \, := \, \left(\begin{array}{rr}0&1\\1&0\\2&1\\3&2\\4&9\\5&44\\6&265\\\end{array}\right)[/math][br][br]Anzahl Permutationen P[sub]n[/sub] mit k Fixpunkten[br]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[br]Anzahl der Permutationen mit genau x Fixpunkten:[br][br][i]Fixn_k(n,x):=nCr(n,x) pn_k(n-x)[/i][br][math]Fixn_k(n, x) \, := \, nCr \left(n,x \right) \; (n-x)! \; \sum_{k=0}^{n-x}\frac{\left(-1 \right)^{k}}{k!}[/math][br][br][i]Anzahl P[sub]6[/sub] mit 2 Fixpunkten[br]Fixn_k(6,2)=135[/i][br][br]Sei Fixn[sub]k[/sub](k) die Anzahl der Permutationen mit genau k Fixpunkten. [br][br][math]\( \sum \limits_{k=0}^{n} k * Fixn_{k}(k)=n ! \)[/math][br][br][i]Sum(j Fixn_k(6,j),j,0,6) == 6![br][br]https://www.mathe-gut-erklaert.de/pdfs/000_Fixpunkte_Perm.pdf[math]\nearrow[/math][/i]