Elementare Kombinatorik/Die Fakultät (N)/Bijektionen/Einführung/Textabschnitt

Aus Wikiversity

Bei einem Tanzkurs mit Damen und Herren gilt heute beim Schneewalzer Damenwahl, wobei die Damen in der Reihenfolge ihrer Sitzordnung wählen dürfen. Die erste Dame hat Wahlmöglichkeiten, die zweite Möglichkeiten, die dritte Möglichkeiten, u.s.w., die vorletze Dame hat noch zwei Möglichkeiten und für die letzte Dame verbleibt eine Möglichkeit.


Definition  

Zu einer natürlichen Zahl nennt man die Zahl

die Fakultät von (sprich Fakultät).

Es ist . Man setzt . Für kleine erhält man die folgende Wertetabelle.



Satz  

Es seien und endliche Mengen, die beide Elemente besitzen.

Dann gibt es bijektive Abbildungen von nach .

Beweis  

Wir führen Induktion über , wobei der Fall klar ist. Die Aussage sei nun für schon bewiesen und es liegen zwei -elementige Mengen und vor. Es sei ein fixiertes Element. Dann gibt es für die Werte genau Möglichkeiten, nämlich die Anzahl der Menge . Wenn dies festgelegt ist, so entsprechen die bijektiven Abbildungen von nach mit

den bijektiven Abbildungen von nach . Nach Induktionsvoraussetzung gibt es solche bijektiven Abbildungen. Daher ist die Anzahl der bijektiven Abbildungen zwischen und gleich


Gleichbedeutend damit ist, dass es Möglichkeiten gibt, Objekte auf Plätze zu verteilen, oder Möglichkeiten, unterscheidbare Kugeln auf unterscheidbare Urnen so zu verteilen, dass keine Urne leer bleibt, oder Möglichkeiten, eine Menge von Objekten abzuzählen (durchzunummerieren).



Korollar  

Auf einer endlichen Menge mit Elementen

gibt es bijektive Abbildungen von nach .

Beweis  

Dies ist ein Spezialfall von Fakt.

Bijektive Abbildungen einer Menge in sich bekommen einen eigenen Namen.


Definition  

Eine Permutation auf einer Menge ist eine bijektive Abbildung


Beispiel  

Wir möchten eine vollständige Liste von allen bijektiven Abbildungen von der Menge in die Menge in der Form von Wertetabellen angeben. Wegen

gibt es sechs solche Abbildungen. Es gibt keine natürliche Reihenfolge dieser Abbildungen, dennoch kann man hier mehr oder weniger systematisch vorgehen. Beispielsweise kann man den Wert an der Stelle zuerst festlegen und dann die möglichen Kombinationen für und durchgehen. Dies führt auf die folgenden Wertetabellen.