Formelsammlung Mathematik: Elementare Kombinatorik

Formelsammlung Mathematik

PermutationenBearbeiten

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:

 

VariationenBearbeiten

Variationen ohne WiederholungBearbeiten

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 WiederholungBearbeiten

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:

 

KombinationenBearbeiten

Kombinationen ohne WiederholungBearbeiten

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 WiederholungBearbeiten

Anzahl der Kombinationen mit Wiederholung (Auswahl von   aus  ):

 

mit   und  .

Twelvefold wayBearbeiten

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