Formelsammlung Mathematik: Elementare Kombinatorik
↑ Formelsammlung Mathematik |
Permutationen
BearbeitenSei 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
BearbeitenVariationen ohne Wiederholung
BearbeitenSei 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
BearbeitenSei 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
BearbeitenKombinationen ohne Wiederholung
BearbeitenKombinationen 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
BearbeitenAnzahl der Kombinationen mit Wiederholung (Auswahl von aus ):
mit und .
Twelvefold way
Bearbeitenbeliebige 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 |