Mathematik: Über Permanenten, Permutationen und Fixpunkte
Released by matroid on Fr. 19. September 2003 18:23:08 [Statistics]
Written by Siah - 7952 x read [Outline] Printable version Printer-friendly version -  Choose language   
Mathematik

\(\begingroup\)

Über Permanenten, Permutationen und Fixpunkte

Hallo,

schon öfter habe ich mich nach einer expliziten Formel (oder mathematisch hochtrabender: „geschlossene Darstellung“ ;-) ), für die Anzahl aller Permutationen einer endlichen Menge, die eine bestimmte Anzahl an Fixpunkten besitzen, umgesehen.
Ich wurde nun selbst fündig, jedoch führte der Weg überraschenderweise an einem determinantenähnlichen Objekt der Matrizenrechnung vorbei, der sog. „Permanente“, deren Theorie in den Lehrbüchern der Linearen Algebra (wohl aufgrund der unterzuordnenden Wichtigkeit im Vergleich zur Determinante) oft vergebens zu suchen ist.
Deswegen folgt nun nach einer kurzen Definition der nötigen Begriffe, gefolgt von einem kleinen Ausflug in die Theorie der Permanenten, bevor wir zum eigentlichen, grundlegenden Satz dieses kleinen Artikels vorstoßen. Angeregt wurde ich auch von Matroids Artikel Derangements revisited.


 

Begriffe, Definitionen

Es sei M:={1,…,n} eine endliche Menge. Unter einer Permutation der Menge M verstehen wir eine bijektive Abbildung der Menge M auf sich. Die Menge aller möglichen Permutationen dieser Menge fassen wir unter dem Namen S_n („Symmetrische Gruppe“) zusammen, welche mit der Hintereinanderausführung von Abbildungen eine Gruppe bildet. Die Mächtigkeit von S_n ist n!.

Unter einem Fixpunkt einer Permutation p verstehen wir ein i aus {1,…,n} mit p(i) = i.

Es sei A eine (n,n)-Matrix über dem Körper K, dann definiert man die Permanente folgendermaßen:

per(A):=sum(a_(1\p(1))*...*a_(n\p(n)),\p\el\ S_n)

Diese Formel erinnert schon stark an die Determinante, aber es fehlt die Berücksichtigung der Vorzeichen der Permutationen. Im Folgenden wollen wir uns einige Gemeinsamsamkeiten und Unterschiede anschauen:
 

Ein Wenig über Permanenten

Da die Definition der Permanente einer Matrix ähnlich zu der der Determinante ist, gibt es natürlich einige Gemeinsamkeiten:

1) per A ist linear in jeder Zeile und Spalte

Beweis: Es ist die Additivität und die Homogenität zu beweisen.

Zur Additivität:
Sei A eine (n,n)-Matrix über K und A_x diejenige Matrix, die aus A hervorgeht, indem man die k-te Zeile durch die Zeile x (x_1, …, x_n) ersetzt. Genau so sei auch A_y erklärt.
Dann ist

per A_(x+y) = sum(a_(1\p(1))*...*a_(k\p(k))*...*a_(n\p(n)),\p\el\ S_n)

Da die k-te Zeile die Einträge x_(1)+y_(1), ..., x_(n)+y_(n) hat,
ist jeder Eintrag a_(k\p(k))=x_(\p(k))+y_(\p(k)). Damit folgt:

sum(a_(1\p(1))*...*a_(k\p(k))*...*a_(n\p(n)),\p\el\ S_n)
=sum(a_(1\p(1))*...*[x_(\p(k))+y_(\p(k)) ]*...*a_(n\p(n)),\p\el\ S_n)
=sum({a_(1\p(1))*...*x_(\p(k))*...*a_(n\p(n))+a_(1\p(1))*...*y_(\p(k))*...*a_(n\p(n)) },\p\el\ S_n)
=sum(a_(1\p(1))*...*x_(\p(k))*...*a_(n\p(n)),\p\el\S_n)
+sum(a_(1\p(1))*...*y_(\p(k))*...*a_(n\p(n)),\p\el\ S_n)
= per A_x + per A_y


Zur Homogenität:

Da die komplette k-te Zeile mit einem Skalar k multilpiziert wird, enthält jeder Summand in der Formel genau einmal den Faktor k. Damit kann man das k vor die Summe ziehen, und die Behauptung steht da.

Der Beweis verläuft analog für die Linearität in den Spalten.

2) Die Permanente einer oberen bzw unteren Dreiecksmatrix ist das Produkt der Elemente auf der Hauptdiagonalen.
Der Beweis verläuft genauso, wie bei Determinanten, wo man sich überlegt, dass von allen möglichen Permutationen nur noch die Identität übrig bleiben kann, und alle anderen Summanden Null werden.

3) Als Folgerung von 2) gilt per E_n = 1

4) Man kann die Permanente einer Matrix auch nach einer Zeile oder Spalte entwickeln, jedoch ist das ein wenig anders, wie von den Determinanten gewohnt, und damit kommen wir nun zu den Unterschieden:
 

Unterschiede zur Determinante:


1) Eine Permanente wird nicht unbedingt Null, wenn der Rang der Matrix nicht voll ist!
Als „Beweis“ könnte man sich überlegen, dass die Determinantenfunktion eindeutig bestimmt ist, und die Permanente schon linear ist, und für die Einheitsmatrix den Wert 1 annimmt. Dann bleibt nur noch diese Eigenschaft übrig, die nicht gelten kann.

2) Die „Entwicklungsformel“ für die Entwicklung nach der j-ten Spalte lautet:
per A=sum(a_ij*per A_ij,i=1,n)

Hier ist A_ij diejenige Matrix ist, die durch Streichung der i-ten Zeile und j-ten Spalte aus A entsteht. Auf einen Beweis verzichte ich an dieser Stelle.

Daraus folgt, dass man die Regeln für die Berechnung der Permanente einer (2,2)-Matrix, bzw einer (3,3)-Matrix aus der Determinantentheorie „ausleihen“ kann, wobei man jedoch mit den Vorzeichen aufpassen muss. Zum Beispiel gilt:

per matrix(a,b;c,d)= a*d+b*c

Und für (3,3)-Matrizen muss man einfach alle negativen Vorzeichen in der „Regel von Sarrus“ durch positive ersetzen.

3) Es sei A eine (n,n)-Matrix über K, und A’ sei die Matrix, die durch Vertauschung zweier Zeilen bzw Spalten aus A entsteht. Dann gilt :

per\ A = per\ A’

Zum Beweis kann man sich folgendes überlegen:
Durch die Vertauschung der k-ten Zeile mit der l-ten Zeile werden alle
Einträge a_(ki) mit a_(li) vertauscht. Da über alle möglichen Permutationen summiert wird, findet durch das Vertauschen lediglich eine Umordnung der Summanden statt.

Dieser kurze Ausflug in das Reich der Permanenten sollte vorerst reichen, um das Hauptergebnis dieses Artikels zu formulieren:
 

Permutationen und Fixpunkte


Zunächst definieren wir zwei Typen von Matrizen:

Die Matrix E_(n,k) entsteht aus der Einheitsmatrix E_n, indem man nur
die ersten k Spalten übernimmt, und die restlichen n-k Spalten
mit Nullspalten auffüllt.

Die Matrix A_(n,k) entsteht aus der Matrix A_n:= matrix(a_ij)_(n\cross\ n) := fdef(0,\ \ i=j;1,\ \ i!=j)
indem man nur die letzten n-k Spalten übernimmt, und die ersten
k Spalten mit Nullspalten auffüllt.


Damit formulieren wir folgenden:
\big\frame\Satz:
Es sei f(n,k) die Anzahl der Permutationen einer n-elementigen Menge
mit genau k Fixpunkten. Weiter seien die Matrizen E_(n,k) und A_(n,k)
wie oben definiert. Dann gilt:

f(n,k)= matrix(n;k)*per (E_(n,k)+A_(n,k))
\frameoff\

Zum Beweis leiten wir die Identität her:
Dazu überlege man sich, dass f(n,0) folgendermaßen berechnet werden kann:

f(n,0) = per A_n =per matrix(0,1,1,..,1;1,0,1,..,1;1,1,0,..,1;.,.,.,..,.;1,1,1,..,0)

Denn f(n,0) ist die Anzahl derjenigen Permutationen, die keinen Fixpunkt haben. Wird nur ein Element auf sich selbst abgebildet, so wird der ganze zugehörige Summand Null, denn auf der Hauptdiagonalen stehen nur Nullen.

Weiter wird überlegt, wie man diejenigen Permutationen zählen kann, die genau einen Fixpunkt besitzen. Dazu wird ein Element festgehalten, nehmen wir mal das erste, und die restlichen Elemente dürfen permutieren, jedoch ohne, dass es einen weiteren Fixpunkt gibt. Die Anzahl entspricht dann

per matrix(1,1,1,..,1;0,0,1,..,1;0,1,0,..,1;.,.,.,..,.;0,1,1,..,0)
Also die erste Spalte entspricht der ersten Spalte der Einheitsmatrix E_n, und die restlichen Spalten entsprechen der oben definierten Matrix A_n.

Es gibt aber n Möglichkeiten ein Element festzuhalten, die zweite sieht so aus:

per matrix(0,0,1,..,1;1,1,1,..,1;1,0,0,..,1;.,.,.,..,.;1,0,1,..,0)

Also entspricht die zweite Spalte gerade der zweiten Spalte der Einheitsmatrix E_n, und die restlichen Spalten entsprechen wieder der Matrix A_n.

Nun überlegt man sich, dass diese n Matrizen durch Zeilen- bzw Spaltenvertauschungen auseinander hervorgehen, und da die Permanenten solcher Matrizen gleich sind, kann man ansetzen:

Es gibt „n über 1“ Möglichkeiten ein Element festzuhalten, also gilt:

f(n,1)=matrix(n;1)* matrix(1,1,1,..,1;0,0,1,..,1;0,1,0,..,1;.,.,.,..,.;0,1,1,..,0)
Das klappt auch für andere k, also kommt man auf die allgemeine Darstellung, wenn man die jeweilige Matrix aus E_(n,k) und A_(n,k) zusammensetzt:

f(n,k)= matrix(n;k)*per (E_(n,k)+A_(n,k))
Und damit ist der Satz bewiesen.
Ich streite nicht ab, dass es andere Möglichkeiten geben mag, diese Anzahl zu berechnen, oder diese Formel zu beweisen, aber ich persönlich finde es erstaunlich, dass schon wieder ein Sachverhalt durch Matrizen ausgedrückt und gelöst werden kann.

Ich hoffe natürlich auf inhaltliche Korrektheit und bin für (konstruktive) Kritik immer offen.

Beste Grüsse
Thorsten

 
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:
: Mathematik :: Permanente :: Permutationen :: Fixpunkte :: Lineare Algebra :: Interessierte Studenten :: Grundstudium Mathematik :
Über Permanenten, Permutationen und Fixpunkte [von Siah]  
Schon öfter habe ich mich nach einer expliziten Formel (oder mathematisch hochtrabender: „geschlossene Darstellung“ ;-) ), für die Anzahl aller Permutationen einer endlichen Menge, die eine bestimmte Anzahl an Fixpunkten besitzen, umgeseh
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
 
Aufrufzähler 7952
 
Aufrufstatistik des Artikels
Insgesamt 454 externe Seitenaufrufe zwischen 2012.01 und 2021.09 [Anzeigen]
DomainAnzahlProz
https://www.bing.com30.7%0.7 %
https://google.de275.9%5.9 %
https://google.com337.3%7.3 %
http://google.de36881.1%81.1 %
https://google.es61.3%1.3 %
https://duckduckgo.com61.3%1.3 %
https://www.ecosia.org40.9%0.9 %
http://suche.t-online.de10.2%0.2 %
http://search.yahoo.com20.4%0.4 %
https://startpage.com10.2%0.2 %
http://google.com10.2%0.2 %
http://de.ask.com10.2%0.2 %
http://www.bing.com10.2%0.2 %

Häufige Aufrufer in früheren Monaten
Insgesamt 429 häufige Aufrufer [Anzeigen]
DatumAufrufer-URL
2012-2017 (115x)http://google.de/url?sa=t&rct=j&q=
201301-01 (43x)http://google.de/url?sa=t&rct=j&q=permutationen mit genau einem fixpunkt
201205-05 (32x)http://google.de/url?sa=t&rct=j&q=varianz genau ein fixpunkt permutation
2020-2021 (31x)https://google.com/
201305-05 (31x)http://google.de/url?sa=t&rct=j&q=permutation fixpunkt sei x
201201-04 (27x)http://google.de/url?sa=t&rct=j&q=signum von permutationen beweis
201405-05 (20x)http://google.de/url?sa=t&rct=j&q=beweis permanente
202102-05 (15x)https://google.de/
201212-12 (13x)http://google.de/url?sa=t&rct=j&q=varianz fixpunkte permutation
201203-03 (12x)http://google.de/url?sa=t&rct=j&q=permutationen signum beweis
201308-08 (11x)http://google.de/url?sa=t&rct=j&q=permanente berechnen
201206-06 (11x)http://google.de/url?sa=t&rct=j&q=vorzeichen permutation
201202-02 (8x)http://google.de/url?sa=t&rct=j&q=permutationen einer 12 elementigen menge
201306-06 (7x)http://google.de/url?sa=t&rct=j&q=errechne permanente
202106-06 (7x)https://google.de/url?sa=t
201311-11 (7x)http://google.de/url?sa=t&rct=j&q=permanente einer matrix
202107-07 (6x)https://google.es
2020-2021 (6x)https://duckduckgo.com/
201304-04 (5x)http://google.de/url?sa=t&rct=j&q=permutationen "summe über produkt"...
201503-03 (5x)http://google.de/url?sa=t&rct=j&q=permanente uebung mathematik
201309-09 (5x)http://google.de/url?sa=t&rct=j&q=anzahl der permutationen mit genau einem fi...
2020-2021 (4x)https://www.ecosia.org/
201208-08 (4x)http://google.de/url?sa=t&rct=j&q=permutation berechnen fixpunkt
202108-08 (4x)https://google.de

[Top of page]

"Mathematik: Über Permanenten, Permutationen und Fixpunkte" | 2 Comments
The authors of the comments are responsible for the content.

Re: Über Permanenten, Permutationen und Fixpunkte
von: shadowking am: Fr. 19. September 2003 21:52:34
\(\begingroup\)Wow! Noch vor drei Wochen hab ich an der gleichen Idee gebastelt, einen eleganten Weg zu finden für die Anzahl der fixpunktfreien Permutationen. Mein Problem war, dass ich es unbedingt mit Determinanten machen wollte und fast daran verzweifelt bin, weil es mit den Vorzeichen nicht hinhauen wollte. Das Signum kriegte ich einfach nicht aus der Formel weg. Der Permanenten-Ansatz ist genau die Idee, die ich hatte, um das Problem zu lösen, und dabei habe ich noch nie was davon gehört! Angeblich gibt es für die Idee ja einen kombinatorischen Zugang, aber den finde ich ziemlich verstiegen.

Weiter so,
Norbert\(\endgroup\)
 

Re: Über Permanenten, Permutationen und Fixpunkte
von: Ex_Mitglied_40174 am: Mi. 21. Januar 2004 16:53:12
\(\begingroup\)was ist ein fixpunkt\(\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]