Mathe für Nicht-Freaks: Abstellraum/Beweis der Rekursionsformel für die Fakultät
Beweis
[Bearbeiten]Wissen wir, dass das Verfahren korrekt ist, können wir nun,von der Art ihrer Erzeugung, auf die Anzahl der erzeugten Anordnungen schließen. Intuitiv sollte die Korrektheit klar sein, der Vollständigkeit halber ist jedoch hierunter ein Beweis angeführt.
Beweis (Progressives Einfügen generiert alle möglichen Anordnungen einer n-elementigen Menge)
Zu zeigen ist, dass das Verfahren genau alle möglichen Anordnungen liefert. Dies kann man in zwei Anforderungen aufspalten:
- Das Verfahren ist surjektiv, d.h. es produziert alle Permutationen
- Das Verfahren ist injektiv d.h. es produziert jede Permutation genau ein Mal.
Wir zeigen zuerst die 1, mit Induktion nach :
Aussageform, deren Allgemeingültigkeit für bewiesen werden soll:
Jede Permutation einer -elementige Menge wird durch progressives Einfügen generiert
1. Induktionsanfang:
Bei der einelementigen Menge liefert das Verfahren als Basisfall die einzige Permutation. .
2. Induktionsschritt:
2a. Induktionsvoraussetzung:
Jede Permutation einer -elementige Menge wird durch progressives Einfügen generiert
2b. Induktionsbehauptung:
Jede Permutation einer -elementige Menge wird durch progressives Einfügen generiert
2c. Beweis des Induktionsschritts:
:
Bemerkung: Eine Anordnung der Elemente einer Menge mit Kardinalität kann man als bijektive Abbildung auffassen, die jeder Position das Element der Menge zuordnet, das diese einnimmt.
Formal: Sei eine beliebige Permutation von Elementen.
Um den Fall auf den Fall zurückzuführen, müssen wir unsere Vorgehnsweise rückwärts anwenden. D.h. wir suchen zu die Permutation von Elementen , die sie nach unserer Vorgehensweise erzeugt. Wir suchen vorerst die Stelle, an der in eingefügt wurde. Formal: Sei das Urbild von . ist also der Form:
Bemerkung: obige Notation ist eine Darstellung einer endlichen Abbildung, wobei die obere Zeile die Elemente der Definitionsmenge, die untere deren entsprechende Bilder darstellt.
Alle Elemente im Bild von rechts von wurden durch das Einfügen von um eins nach rechts verschoben. Formal:
Dann sieht so aus:
Laut IV wird als Permutation von Elementen durch das Verfahren erzeugt. wird im Verfahren also durch das Einfügen von in an Position erzeugt.
Es verbleibt zu zeigen 2. Wir zeigen die Aussage auch mit Induktion.
Aussageform, deren Allgemeingültigkeit für bewiesen werden soll:
Progressives Einfügen produziert nur unterschiedliche Permutation einer -elementigen Menge
1. Induktionsanfang:
Es gibt genau eine Permutation der einelementigen Menge, die wir produzieren.
2. Induktionsschritt:
2a. Induktionsvoraussetzung:
Progressives Einfügen produziert nur unterschiedliche Permutation einer -elementigen Menge
2b. Induktionsbehauptung:
Progressives Einfügen produziert nur unterschiedliche Permutation einer -elementigen Menge
2c. Beweis des Induktionsschritts:
Mit der IV produziert unser Verfahren nur unterschiedliche Permutationen einer -elementigen Menge. Zu untersuchen ist ob wir im Induktionsschritt Duplikate erzeugen. In Frage kämen auf jeden Fall nur Permutationen, in denen an der gleichen Stelle eingefügt wurde. Wären jedoch zwei solche Permutationen gleich, so hätten die Permutationen der Länge , aus denen sie entstanden, auch gleich sein müssen! Widerspruch zur IV, somit gilt die Aussage