Derangements revisited

Die Anzahl der ungeraden Permutationen ohne Fixpunkt ist gleich der Anzahl der Permutationen mit genau zwei Fixpunkten.

Definitionen und Vorbereitungen

\fedon\mixonEin \big\Derangement \normal\ist eine Permutation von n Elementen, in der
kein Element auf sich selbst abgebildet wird.
Die Anzahl solcher Permutationen, also der Derangements von menge(1,...,n),
\fedoffbezeichne mit D_n\ .

Es gilt (bekanntlich):
\fedon\mixon
\ll(1)D_n=(n-1)*(D_(n-1)+D_(n-2))
\fedoff\ll(2)D_n=n*D_(n-1)+(-1)^n
Ich werde diese beiden Aussagen weiter unten beweisen.

Die Folge der Derangement-Zahlen ist katalogisiert in The On-Line Encyclopedia of Integer Sequences (kurz: Sloane's) als A000166.

Anmerkungen: Ein Derangement ist eine fixpunktlose Permutation.
'Derangement' kann man mit 'Unordnung' übersetzen.

\fed\mixonSei f(n,k) die Anzahl der Permutationen von n Elementen mit genau k Fixpunkten.

\fed\mixon\ll(3) Es gilt (selbstverständlich): D_n=f(n,0).

Gerade und ungerade Permutationen

Man unterscheidet gerade und ungerade Permutationen. Eine Permutation ist gerade, wenn sie das Produkt von gerade vielen Transpositionen (Vertauschungen zweier Elemente) ist. Ansonsten ist sie ungerade. Man weiß, daß sich jede Permutation in ein Produkt von Transpositionen zerlegen läßt, und hat man zwei Zerlegungen, dann ist die Länge bei beiden entweder gerade oder ungerade.
Die Permutationen mit genau k Fixpunkten kann man sortieren (d.h. disjunkt aufteilen) in gerade und ungerade Permutationen mit genau k Fixpunkten.

Ich führe Bezeichnungen ein:

\fedon\mixon Eine n\-Permutation ist eine Permutation von n Elementen.
f^\+(n,k) bezeichne die Anzahl der geraden n\-Permutationen mit genau k Fixpunkten.
\fedoff f^\-(n,k) bezeichne die Anzahl der ungeraden n\-Permutationen mit genau k Fixpunkten.

Offensichtlich ist
\fed\mixon\ll(4) f(n,k) = f^\+(n,k)+f^\-(n,k)

Zur weiteren Motivation

\fed\mixonDie Folge f^\-(n,0) ist bei Sloane's registriert als
     A000387.
\fed\mixonDie Folge f^\+(n,0) ist bei Sloane's registriert als
      A003221.

Zu A000387 sagt die dortige Beschreibung, daß es sich um die Anzahl der Permutationen mit genau zwei Fixpunkten handelt. Nicht erwähnt ist, daß A000387 zugleich die Anzahl der ungeraden Permutationen ohne Fixpunkte ist. Diese Lücke möchte ich nun schließen, indem ich den Beweis gebe.
Die Summe A000387(n)+A003221(n) ist also gleich D_n.

Wiederholung bekannter Definitionen

Damit sie nicht unbekannt seien, hier einige weitere Definitionen und Schreibweisen, die ich verwenden werde:
\fedon\mixon
i. Das \big\Signum \normal\einer Permutation \p ist 1, wenn \p gerade ist, sonst \-1.
Abgekürzt: sign(\p)=fdef( 1, \p gerade;\-1, \p ungerade)

ii. Die \big\Determinante \normal\einer Matrix A = (a_ij)_(n\cross\ n) ist gleich:
det(A):=sum(sign(\p)*a_(1\p(1))*...*a_(n\p(n)),\p\el\ S_n)
\small [S_n ist die Symmetrische Gruppe vom Grad n, das ist nichts anderes, als die
\small Menge der n\-Permutationen.]

iii. Die \big\Permanente \normal\einer Matrix A = (a_ij)_(n\cross\ n) ist gleich:
\fedoff per(A):=sum(a_(1\p(1))*...*a_(n\p(n)),\p\el\ S_n)

Zählen mit Permanenten und Determinanten

Ich werde Permutationen und Derangements mit Hilfe von Matrizen darstellen und zählen. Die Anzahlberechnung benutzt Determinanten und Permanenten dieser Matrizen.

Aussagen über Permutationen und Matrizen

\fedon\mixonmakro(mymatrix,(array(%{*})||)
Sei A_n die Matrix mymatrix(a_ij)_(n\cross\ n)=fdef(0,\ \ i=j;1,\ \ i!=j)

Ausgeschrieben:

A_n=mymatrix(0,1,1,..,1;1,0,1,..,1;1,1,0,..,1;.,.,.,..,.;1,1,1,..,0)

Dann ist

\ll(5) D_n = per(A_n)
\ll(6) f^\+(n,0)-f^\-(n,0)=(-1)^(n-1)*(n-1)=det(A_n)
\fedoff\ll(7) f^\+(n,k)-f^\-(n,k)=(n;k)*det(A_(n-k))

\fedon\mixonBeweis__ \ref(5): Eine Permutation \p zählt in per(A_n) genau dann,
wenn alle a_(i\p(i)) gleich 1 sind. Da die Diagonaleinträge a_ii gleich 0 sind,
zählt keine Permutation, die ein Element auf sich selbst abbildet, aber
es zählen alle Permutationen, die kein Element auf sich selbst abbilden.
\stress\qed \ref(5).
\fedoff

\fedon\mixonBeweis__ \ref(6): In der Determinante zählen die geraden Permutationen
ohne Fixpunkt mit \+1 und die ungeraden Permutationen mit \-1.
Für k=0 gilt somit
f^\+(n,0)-f^\-(n,0)=det(A_n).
Das beweist die eine Gleichheit. Nun ist noch der Wert der Determinante
zu berechnen.
Bekanntlich ist die Determinante eine in jeder Zeile lineare Abbildung, und
ihr Wert ändert sich nicht, wenn man das Vielfache einer Zeile zu einer
anderen Zeile addiert.
Addiert man in A_n das -1/(n-2) \-fache der Zeilen 2 bis n zur ersten Zeile,
\fedoffdann wird (exemplarisch für n=5):
\fedonuselib(common,1)
det(0,1,1,1,1;1,0,1,1,1;1,1,0,1,1;1,1,1,0,1;1,1,1,1,0)

\ \ \ \ zu

\fedoffdet(-4/3,0,0,0,0;1,0,1,1,1;1,1,0,1,1;1,1,1,0,1;1,1,1,1,0)
\fedon\mixonEs ist somit det(A_n)=-(n-1)/(n-2)*det(A_(n-1)).
Anfangswerte der Folge der Determinantenwerte sind

det(A_1)=1 und det(A_2)=-1.
\fedoff\stress\qed \ref(6).

\fedon\mixonBeweis__ \ref(7):
Für k>0 betrachte Permutationen mit genau k Fixpunkten.
Unter den n Elementen der Grundmenge kann man auf (n;k) Weisen
genau k Elemente aussuchen, die durch \p auf sich selbst abgebildet
werden. Elemente die in einer Permutation fix sind, beeinflussen das
Signum der Permutation nicht.
Die übrigen n-k Elemente dürfen nicht auf sich selbst abgebildet werden,
d.h. eingeschränkt auf diese n-k Elemente liegt ein Derangement vor.
Die folgende Matrix beschreibt die Permutationen mit genau k (ausgewählten)
Fixpunkten (o.B.d.A. seien die Elemente 1,2,...,k fix):
\fedoff
\fedonuselib(common,1)
makro(mymatrix,(array(%{*})||
define(ar01,array( 1,0,...,0;0,1,...,0;.,.,...,.;0,0,...,1))
define(ar00,array(\ ,\ ,\big 0,\ ,\ ))
A_(n,k)=mymatrix(\ar01,\ar00;\ar00, array( 0,1,..,1; 1,0,..,1; .,.,...,.; 1,1,..,0))
\fedoff
\fedon\mixonDie Determinante dieser Matrix ist gleich det(A_(n-k)), und wenn man in
die zuvor schon bewiesenen Gleichung \ref(6) nun n-k für n einsetzt,
findet man:
f^\+(n-k,0)-f^\-(n-k,0)=(-1)^(n-k-1)*(n-k-1)=det(A_(n-k)).
Mit dem Faktor (n;k), der die verschiedenen Möglichkeiten zählt, genau
k Elemente fix zu halten, folgt die Behauptung.
\fedoff\stress\qed \ref(7)

\fedon\mixon\boxon\light\big\ Satz: Es gilt:
\ll(8) f^\-(n,0)=f(n,2)
\normal\ d.h. die Anzahl der Permutationen mit genau zwei Fixpunkten
ist gleich der Anzahl der ungerade Permutationen ohne Fixpunkt.
\fedoff

Beweis der Aussagen (1) und (2)

\fedon\mixonAls Hilfsmittel für den Beweis des Satzes zeige nun \ref(1) und \ref(2):

Beweis__ \ref(1): Behauptung: D_n=(n-1)*(D_(n-1)+D_(n-2))
Nach \ref(5) ist D_n=per(A_n).
Die Permanente kann man \- genau wie von der Determinante bekannt \- nach
einer Zeile oder Spalte entwickeln.

Bei Entwicklung nach der ersten Zeile ergibt sich:
\fedoff
\fed\big (9)
\fedonmakro(mymatrix,array(%{*})||)
\fedoff\ \ \ \ \ D_n=(n-1)*per(mymatrix(1,1,...,1;1,0,...,1;.,.,...,.;1,1,...,0))_((n-1)\cross (n-1))
Nun steckt hinter dieser Permanente ein kombinatorisches Problem.
Es geht um Permutationen, und in der ersten Spalte stehen nur Einsen, d.h. diese Permanente zählt die Möglichkeiten das Element 1 beliebig und keines der Elemente 2 bis n auf sich selbst abzubilden.
Die hier auftretenden Permutationen kann man disjunkt aufteilen auf die Fälle
      a. die 1 auf 1 abzubilden, und
      b. die 1 nicht auf 1 abzubilden.

Ausgedrückt in Permantenten bedeutet das:

\fedonmakro(mymatrix,array(%{*})||)
per(mymatrix(1,1,...,1;1,0,...,1;.,.,...,.;1,1,...,0))= per(mymatrix(1,0,...,0;0,0,...,1;.,.,...,.;0,1,...,0))+per(mymatrix(0,1,...,1;1,0,...,1;.,.,...,.;1,1,...,0))
\fedoff
\fedon\mixonDie erste Permanente hat den Wert D_(n-2) .
Die zweite Permanente hat den Wert D_(n-1) .

Eingesetzt in \ref(9) ist das die Behauptung:

D_n = (n-1)*(D_(n-2)+D_(n-1))
\fedoff\stress\qed \ref(1).

\fedon\mixonBeweis__ \ref(2): Aus \ref(1) folgt durch Umordnen:

D_n=n*D_(n-1)+n*D_(n-2)-D_(n-1)-D_(n-2)\ ,
und weiter:
\ll(10) D_n-n*D_(n-1)=-D_(n-1)+(n-1)*D_(n-2)

Setzt man
\ll(11) b_n:=D_n-n*D_(n-1)\ ,
dann lautet \ref(10) nun:
\ll(12) b_n=-b_(n-1)

Es ist
\ll(13) b_1=D_1-1*D_0=0-1=-1
und somit
\ll(14) b_n=(-1)^n\ ,
Aus \ref(11) und \ref(14) folgt die Behauptung.
\fedoff\stress\qed \ref(2).

Beweis des Satzes

Wir kommen nun zum Beweis des Satzes (8):
\fedon\mixon f^\-(n,0) = f(n,2)
\fedoffEs gehen alle zuvor bewiesenen Aussagen in den Beweis ein.

\fedon\mixonWir schreiben gemäß \ref(4) unter Verwendung
von \ref(3) sowie \ref(6) untereinander:
\ll(15) f^\+(n,0)+f^\-(n,0) = D_n
\ll(16) f^\+(n,0)-f^\-(n,0)=(-1)^(n-1)*(n-1)
Subtrahiert man \ref(16) von \ref(15) erhält man:

\ll(17) 2*f^\-(n,0)=D_n-(-1)^(n-1)*(n-1)
\ll(17.1) =D_n-(-1)^n-n*(-1)^(n-1)
Einsetzen von \ref(2) in \ref(17.1):
=n*D_(n-1)-n*(-1)^(n-1)
\ll(17.2) =n*(D_(n-1)-(-1)^(n-1))
Nochmal Einsetzen von \ref(2) ergibt
\ll(17.3) =n*(n-1)*D_(n-2)

\big\Zusammenfassend:
f^\-(n,0)=(n;2)*D_(n-2)
Argumentiert man wie im Beweis von \ref(7), findet man:
(n;2)*D_(n-2) ist gleich der Anzahl der Permutationen mit genau
zwei Fixpunkten.
\stress\qed \ref(8).
\fedoff

Ja, der Beweis ist streckenweise technisch, hat aber seine kombinatorischen Momente. Es mag andere Beweise geben, aber ich wollte das verwenden, was in der letzten Woche im Forum eine Rolle gespielt hat. Falls sich jemand fragt, wozu Permanenten gut sind, hier hat er ein Beispiel.