Mathe für Nicht-Freaks: Abstellraum/Beweis der Rekursionsformel für die Fakultät

Beweis

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:

1. Das Verfahren ist surjektiv, d.h. es produziert alle Permutationen
2. Das Verfahren ist injektiv d.h. es produziert jede Permutation genau ein Mal.

Wir zeigen zuerst die 1, mit Induktion nach $n$:

Aussageform, deren Allgemeingültigkeit für $m\in \mathbb {N}$ bewiesen werden soll:

Jede Permutation einer $m$-elementige Menge wird durch progressives Einfügen generiert

1. Induktionsanfang:

Bei der einelementigen Menge liefert das Verfahren als Basisfall die einzige Permutation. $\square$.

2. Induktionsschritt:

2a. Induktionsvoraussetzung:

Jede Permutation einer $n$-elementige Menge wird durch progressives Einfügen generiert

2b. Induktionsbehauptung:

Jede Permutation einer $n+1$-elementige Menge wird durch progressives Einfügen generiert

2c. Beweis des Induktionsschritts:

$n\to n+1$:

Bemerkung: Eine Anordnung der Elemente einer Menge $M$ mit Kardinalität $n$ kann man als bijektive Abbildung $\{1,\dots ,n\}\to M$ auffassen, die jeder Position das Element der Menge $M$ zuordnet, das diese einnimmt.

Formal: Sei $\tau$ eine beliebige Permutation von $n+1$ Elementen.

Um den Fall $n+1$ auf den Fall $n$ zurückzuführen, müssen wir unsere Vorgehnsweise rückwärts anwenden. D.h. wir suchen zu $\tau$ die Permutation von $n$ Elementen $\phi$, die sie nach unserer Vorgehensweise erzeugt. Wir suchen vorerst die Stelle, an der $n+1$ in $\phi$ eingefügt wurde. Formal: Sei $i$ das Urbild von $n+1$. $\tau$ ist also der Form:

${\begin{pmatrix}1&\dots &i&\dots &n+1\\\tau (1)&\dots &n+1&\dots &\tau (n+1)\end{pmatrix}}$

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 $\phi$ rechts von $i$ wurden durch das Einfügen von $n+1$ um eins nach rechts verschoben. Formal:

${\mbox{Wähle }}\phi :\mathbb {N} \to \mathbb {N} :\phi (j)={\begin{cases}\tau (j)\ &,1\leq j<i\\\tau (j+1)\ &,i\leq j\leq n\end{cases}}$ Dann sieht $\phi$ so aus:

${\begin{pmatrix}1&\dots &i&i+1&\dots &n\\\tau (1)&\dots &\tau (i+1)&\tau (i+2)&\dots &\tau (n+1)\end{pmatrix}}$

Laut IV wird $\phi$ als Permutation von $n$ Elementen durch das Verfahren erzeugt. $\tau$ wird im Verfahren also durch das Einfügen von $n+1$ in $\phi$ an Position $i$ erzeugt. $\quad \square$

Es verbleibt zu zeigen 2. Wir zeigen die Aussage auch mit Induktion.

Aussageform, deren Allgemeingültigkeit für $m\in \mathbb {N}$ bewiesen werden soll:

Progressives Einfügen produziert nur unterschiedliche Permutation einer $m$-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 $n$-elementigen Menge

2b. Induktionsbehauptung:

Progressives Einfügen produziert nur unterschiedliche Permutation einer $n+1$-elementigen Menge

2c. Beweis des Induktionsschritts:

Mit der IV produziert unser Verfahren nur unterschiedliche Permutationen einer $n$-elementigen Menge. Zu untersuchen ist ob wir im Induktionsschritt Duplikate erzeugen. In Frage kämen auf jeden Fall nur Permutationen, in denen $n+1$ an der gleichen Stelle eingefügt wurde. Wären jedoch zwei solche Permutationen gleich, so hätten die Permutationen der Länge $n$, aus denen sie entstanden, auch gleich sein müssen! Widerspruch zur IV, somit gilt die Aussage$\quad \square$