Mathematik: Derangements revisited
Released by matroid on Sa. 31. Mai 2003 02:56:08 [Statistics]
Written by matroid - 4501 x read [Outline] Printable version Printer-friendly version -  Choose language   
Mathematik

\(\begingroup\)\(\newcommand{\IX}{\mathbb{X}} \newcommand{\IW}{\mathbb{M}} \newcommand{\politician}[1]{\text{Ich habe die Frage nicht verstanden. #1}} \newcommand{\ba}{\begin{aligned}} \newcommand{\ea}{\end{aligned}} \newcommand{\bpm}{\begin{pmatrix}} \newcommand{\epm}{\end{pmatrix}} \newcommand{\bc}{\begin{cases}} \newcommand{\ec}{\end{cases}} \newcommand{\on}{\operatorname} \newcommand{\ds}{\displaystyle}\)

Derangements revisited

Forum-Beiträge der letzten Woche haben mich dazu angeregt, eine Verbindung von Kombinatorik, Permutationen, Matrizen, Determinanten und Permanenten zu erkennen, und darüber zu schreiben. Nach den notwendigen Vorbereitungen beweise ich das Hauptergebnis:
Die Anzahl der ungeraden Permutationen ohne Fixpunkt ist gleich der Anzahl der Permutationen mit genau zwei Fixpunkten.
Ich danke sastra, daß er mich mit der Nase darauf gestoßen hat (Forumthema Permutationen ohne Fixpunkte). Ein früherer Artikel über Derangements findet sich hier.

Definitionen und Vorbereitungen

Ein \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),
bezeichne mit D_n\ .

Es gilt (bekanntlich):

\ll(1)D_n=(n-1)*(D_(n-1)+D_(n-2))
\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.

Ein i aus menge(1,...,n) heißt \big\Fixpunkt \normal\der Permutation \p, wenn \p(i)=i.

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

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

\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:

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

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

Zur weiteren Motivation

Die Folge f^\-(n,0) ist bei Sloane's registriert als
     A000387.
Die 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 Dn.

Wiederholung bekannter Definitionen

Damit sie nicht unbekannt seien, hier einige weitere Definitionen und Schreibweisen, die ich verwenden werde:

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:
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

makro(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)
\ll(7) f^\+(n,k)-f^\-(n,k)=(n;k)*det(A_(n-k))

Beweis__ \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).


Beweis__ \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,
dann wird (exemplarisch für n=5):
uselib(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

det(-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)
Es 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.
\stress\qed \ref(6).

Beweis__ \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):

uselib(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))

Die 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.
\stress\qed \ref(7)

\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.

Beweis der Aussagen (1) und (2)

Als 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:

\big (9)
makro(mymatrix,array(%{*})||)
\ \ \ \ \ 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:

makro(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))

Die 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))
\stress\qed \ref(1).

Beweis__ \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.
\stress\qed \ref(2).

Beweis des Satzes

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

Wir 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).


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.

Matroid 2003


 
Dieser Artikel ist enthalten in unserem Buch
Mathematisch für fortgeschrittene Anfänger
Mathematisch für fortgeschrittene Anfänger

\(\endgroup\)
Get link to this article Get link to this article  Printable version Printer-friendly version -  Choose language     Kommentare zeigen Comments  
pdfFür diesen Artikel gibt es keine pdf-Datei


Arbeitsgruppe Alexandria Dieser Artikel ist im Verzeichnis der Arbeitsgruppe Alexandria eingetragen:
: Lineare Algebra :: Unterhaltsame Mathematik :: Grundstudium Mathematik :: Mathematik :: Permanente :: Permutationen :: Kombinatorik :: Derangement :
Derangements revisited [von matroid]  
Forum-Beiträge der letzten Woche haben mich dazu angeregt, eine Verbindung von Kombinatorik, Permutationen, Matrizen, Determinanten und Permanenten zu erkennen, und darüber zu schreiben. Nach den notwendigen Vorbereitungen beweise ich das Hauptergebnis: Die Anzahl der ungeraden Permutationen ohne Fixpunkt ist gleich der Anzahl der Permutationen mit genau zwei Fixpunkten.
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
 
Aufrufzähler 4501
 
Aufrufstatistik des Artikels
Insgesamt 92 externe Seitenaufrufe zwischen 2012.01 und 2021.09 [Anzeigen]
DomainAnzahlProz
https://google.com1718.5%18.5 %
https://matheplanet.com11.1%1.1 %
https://de.m.wikipedia.org22.2%2.2 %
https://de.wikipedia.org22.2%2.2 %
http://google.de5964.1%64.1 %
https://google.de44.3%4.3 %
https://www.bing.com22.2%2.2 %
http://google.com22.2%2.2 %
http://google.ch22.2%2.2 %
http://de.ask.com11.1%1.1 %

Häufige Aufrufer in früheren Monaten
Insgesamt 69 häufige Aufrufer [Anzeigen]
DatumAufrufer-URL
2013-2015 (30x)http://google.de/url?sa=t&rct=j&q=
201205-05 (16x)http://google.de/url?sa=t&rct=j&q=kombinatorik derangement
2020-2021 (15x)https://google.com/
201202-10 (4x)http://google.de/url?sa=t&rct=j&q=derangement beweis
202105-05 (4x)https://google.de

[Top of page]

"Mathematik: Derangements revisited" | 6 Comments
The authors of the comments are responsible for the content.

Re: Derangements revisited
von: matroid am: So. 01. Juni 2003 22:18:19
\(\begingroup\)Meine kleine Ergänzung ist nun auch in A000387 vermerkt.

Gruß
Matroid\(\endgroup\)
 

Re: Derangements revisited
von: sastra am: Mo. 02. Juni 2003 11:55:10
\(\begingroup\)Cool, d.h. mein Beitrag 'Permutationen ohne Fixpunkte', ist nun mit der On-Line Encyclopedia of Integer Sequences verlinkt. 😄
Die Frage, die sich mir stellt, ist nun:
Gibt es auch zu diesem Satz einen Beweis, der auf Paarbildung beruht ?
\(\endgroup\)
 

Re: Derangements revisited
von: matroid am: Mo. 02. Juni 2003 12:04:53
\(\begingroup\)Wie hieß noch mal diese Aussage?

Sie besagt, daß für je zwei Menschen auf der Welt eine Kette gebildet werden kann - mit diesen beiden Menschen an den Enden und weiteren Menschen dazwischen, so daß je zwei benachbarte Menschen sich zuvor schon einmal die Hand gegeben haben.
Und dann besagt diese Theorie, daß die Kette nie oder selten länger als 6 Menschen sein muß.

Und dann waren da noch die Erdös-Zahlen.

Gruß
Matroid\(\endgroup\)
 

Re: Derangements revisited
von: Ex_Mitglied_40174 am: So. 16. November 2003 17:05:53
\(\begingroup\)was hat das mit potenzen zu tun? hab auch ka bilder!\(\endgroup\)
 

Re: Derangements revisited
von: Ex_Mitglied_40174 am: Mo. 27. November 2006 12:13:23
\(\begingroup\)Weiß jemand ein Tool für Permutations- berechnung ? Vielen Dank den Text muß ich mir ein paar mal reinziehen zum verdauen.\(\endgroup\)
 

Re: Derangements revisited
von: matroid am: Di. 28. November 2006 20:20:57
\(\begingroup\)Hi, hier ist eine Site, da kann man Permutationen erzeugen lassen: theory.cs.uvic.ca/gen/perm.html Man kann dort auch den Source bekommen, hier: theory.cs.uvic.ca/inf/perm/PermInfo.html Neben Permutationen beschäftigt sich die Site mit vielen anderen Zähl- und Anordnungsproblemen. Gruß Matroid\(\endgroup\)
 

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]