Formelsammlung Mathematik: Elementare Kombinatorik
↑ Formelsammlung Mathematik |
Permutationen Bearbeiten
Sei die Menge der Bijektionen von nach . Sei eine endliche Menge mit .
Eine Abbildung heißt Permutation. Es gilt die Gruppenisomorphie .
Anzahl der Permutationen:
Die Funktion heißt Fakultät und ist rekursiv definiert:
Es gilt:
Variationen Bearbeiten
Variationen ohne Wiederholung Bearbeiten
Sei die Menge der Injektionen von nach . Sei und .
Aus unterschiedlichen Karten wird eine Auswahl auf eine Anordnung von Plätzen gelegt. Anders formuliert: Eine Injektion ordnet jedem Platz eine Karte zu. Man nennt eine Variation ohne Wiederholung von Karten zur Klasse .
Anzahl der Variationen ohne Wiederholung:
Variationen mit Wiederholung Bearbeiten
Sei die Menge der Abbildungen von nach . Sei und .
Aus unterschiedlichen Karten wird eine Auswahl auf eine Anordnung von Plätzen gelegt, wobei eine Karte mehrmals vorkommen darf. Anders formuliert: Eine Abbildung ordnet jedem Platz eine Karte zu. Man nennt eine Variation mit Wiederholung von Karten zur Klasse .
Anzahl der Variationen mit Wiederholung:
Kombinationen Bearbeiten
Kombinationen ohne Wiederholung Bearbeiten
Kombinationen sind Variationen ohne Wiederholung, wobei die Reihenfolge der Plätze keine Rolle mehr spielt. Um den Verlust der Information über die Reihenfolge zu erreichen, definiert man die Äquivalenzrelation
Ist eine Injektion, so wird die Äquivalenzklasse
Kombination ohne Wiederholung genannt. Es handelt sich dabei um einen Orbit, weil eine Gruppenaktion ist.
Anzahl der Kombinationen ohne Wiederholung (Auswahl von aus ):
mit und .
Kombinationen mit Wiederholung Bearbeiten
Anzahl der Kombinationen mit Wiederholung (Auswahl von aus ):
mit und .
Twelvefold way Bearbeiten
beliebige f | injektive f | surjektive f | |
---|---|---|---|
fallende Faktorielle | |
Binomialkoeffizient | |
Stirling-Zahl zweiter Art | |
Anzahl der Partitionen von in genau Teile | |
Iverson-Klammern ([falsch]=0, [wahr]=1) | |
symmetrische Gruppe |