Die Mathe-Redaktion - 16.01.2018 23:56 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
Listenpunkt3 im Schwätz / Top 15
ListenpunktWerde Mathe-Millionär!
ListenpunktZur Award-Abstimmung
ListenpunktFormeleditor fedgeo
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden oder den Newsletter bestellen.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 478 Gäste und 21 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Mathematik: Über Permanenten, Permutationen und Fixpunkte
Freigegeben von matroid am Fr. 19. September 2003 18:23:08
Verfasst von Siah -   7628 x gelesen [Gliederung] [Statistik] Druckbare Version Druckerfreundliche Version
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:

fed-Code einblenden

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

fed-Code einblenden

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:
fed-Code einblenden

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:

fed-Code einblenden

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 :

fed-Code einblenden

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:

fed-Code einblenden

fed-Code einblenden

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

fed-Code einblenden

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

fed-Code einblenden
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:

fed-Code einblenden

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:

fed-Code einblenden
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:

fed-Code einblenden
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\)

Link auf diesen Artikel Link auf diesen Artikel  Druckbare Version Druckerfreundliche Version  Einen Freund auf diesen Artikel aufmerksam machen Weitersagen Kommentare zeigen Kommentare  
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]

 
Verwandte Links
 
Besucherzähler 7628
 
Aufrufstatistik des Artikels
Insgesamt 377 externe Besuche zwischen 2018.01 und 2018.01 [Anzeigen]
DomainAnzahlProz
http://matheplanet.com30.8%0.8 %
http://google.de36897.6%97.6 %
http://search.yahoo.com20.5%0.5 %
http://www.bing.com10.3%0.3 %
http://google.com10.3%0.3 %
http://suche.t-online.de10.3%0.3 %
http://de.ask.com10.3%0.3 %

Aufrufer der letzten 5 Tage im Einzelnen
Insgesamt 3 Aufrufe in den letzten 5 Tagen. [Anzeigen]
DatumAufrufer-URL
2018.01.02-2018.01.16 (3x)https://www.google.de/

Häufige Aufrufer in früheren Monaten
Insgesamt 356 häufige Aufrufer [Anzeigen]
DatumAufrufer-URL
2012-2017 (115x)http://google.de/url?sa=t&rct=j&q=
2013.01 (43x)http://google.de/url?sa=t&rct=j&q=permutationen mit genau einem fixpunkt
2012.05 (32x)http://google.de/url?sa=t&rct=j&q=varianz genau ein fixpunkt permutation
2013.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
2014.05 (20x)http://google.de/url?sa=t&rct=j&q=beweis permanente
2012.12 (13x)http://google.de/url?sa=t&rct=j&q=varianz fixpunkte permutation
2012.03 (12x)http://google.de/url?sa=t&rct=j&q=permutationen signum beweis
2012.06 (11x)http://google.de/url?sa=t&rct=j&q=vorzeichen permutation
2013.08 (11x)http://google.de/url?sa=t&rct=j&q=permanente berechnen
2012.02 (8x)http://google.de/url?sa=t&rct=j&q=permutationen einer 12 elementigen menge
2013.06 (7x)http://google.de/url?sa=t&rct=j&q=errechne permanente
2013.11 (7x)http://google.de/url?sa=t&rct=j&q=permanente einer matrix
2013.04 (5x)http://google.de/url?sa=t&rct=j&q=permutationen "summe über produkt"...
2015.03 (5x)http://google.de/url?sa=t&rct=j&q=permanente uebung mathematik
2013.09 (5x)http://google.de/url?sa=t&rct=j&q=anzahl der permutationen mit genau einem fi...
2012.08 (4x)http://google.de/url?sa=t&rct=j&q=permutation berechnen fixpunkt

[Seitenanfang]

" Mathematik: Über Permanenten, Permutationen und Fixpunkte" | 2 Kommentare
 
Für den Inhalt der Kommentare sind die Verfasser verantwortlich.

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

 [Bearbeiten]

Re: Über Permanenten, Permutationen und Fixpunkte
von Ex_Mitglied_40174 am Mi. 21. Januar 2004 16:53:12

\(\begingroup\)
was ist ein fixpunkt\(\endgroup\)

 [Bearbeiten]

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2017 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. 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]