Formelsammlung Mathematik: Elementare Kombinatorik

↑ Formelsammlung Mathematik

Permutationen

Sei $\mathrm {Bij} (A,B)$ die Menge der Bijektionen von $A$ nach $B$. Sei $M$ eine endliche Menge mit $n=|M|$.

Eine Abbildung $\pi \in \mathrm {Bij} (M,M)$ heißt Permutation. Es gilt die Gruppenisomorphie $\mathrm {Bij} (M,M)\simeq S_{n}$.

Anzahl der Permutationen:

$|\mathrm {Bij} (M,M)|=|S_{n}|=n!.$

Die Funktion $f(n)=n!$ heißt Fakultät und ist rekursiv definiert:

$0!:=1,$

$n!:=n\cdot (n-1)!.$

Es gilt:

$n!=\prod _{k=1}^{n}k=1\cdot 2\cdot 3\cdot \ldots \cdot (n-1)\cdot n.$

Variationen

Variationen ohne Wiederholung

Sei $\mathrm {Inj} (D,Z)$ die Menge der Injektionen von $D$ nach $Z$. Sei $n=|Z|$ und $k=|D|$.

Aus $n$ unterschiedlichen Karten wird eine Auswahl auf eine Anordnung von $k$ Plätzen gelegt. Anders formuliert: Eine Injektion $f$ ordnet jedem Platz eine Karte zu. Man nennt $f$ eine Variation ohne Wiederholung von $n$ Karten zur Klasse $k$.

Anzahl der Variationen ohne Wiederholung:

$|\mathrm {Inj} (D,Z)|=n^{\underline {k}}={\frac {n!}{(n-k)!}}=k!\cdot {\binom {n}{k}}.$

Variationen mit Wiederholung

Sei $\mathrm {Abb} (D,Z)$ die Menge der Abbildungen von $D$ nach $Z$. Sei $n=|Z|$ und $k=|D|$.

Aus $n$ unterschiedlichen Karten wird eine Auswahl auf eine Anordnung von $k$ Plätzen gelegt, wobei eine Karte mehrmals vorkommen darf. Anders formuliert: Eine Abbildung $f$ ordnet jedem Platz eine Karte zu. Man nennt $f$ eine Variation mit Wiederholung von $n$ Karten zur Klasse $k$.

Anzahl der Variationen mit Wiederholung:

$|\mathrm {Abb} (D,Z)|=n^{k}.$

Kombinationen

Kombinationen ohne Wiederholung

Kombinationen sind Variationen ohne Wiederholung, wobei die Reihenfolge der $k$ Plätze keine Rolle mehr spielt. Um den Verlust der Information über die Reihenfolge zu erreichen, definiert man die Äquivalenzrelation

$f\sim g\;:\Longleftrightarrow \;\exists \pi \in S_{k}\colon f\circ \pi =g.$

Ist $f$ eine Injektion, so wird die Äquivalenzklasse

$f\circ S_{k}:=\{f\circ \pi \mid \pi \in S_{k}\}$

Kombination ohne Wiederholung genannt. Es handelt sich dabei um einen Orbit, weil $f\circ \pi$ eine Gruppenaktion ist.

Anzahl der Kombinationen ohne Wiederholung (Auswahl von $k$ aus $n$):

$|\{f\circ S_{k}\mid f\in \mathrm {Inj} (D,Z)\}|={\binom {n}{k}}={\frac {n!}{k!\cdot (n-k)!}}$

mit $n=|Z|$ und $k=|D|$.

Kombinationen mit Wiederholung

Anzahl der Kombinationen mit Wiederholung (Auswahl von $k$ aus $n$):

$|\{f\circ S_{k}\mid f\in \mathrm {Abb} (D,Z)\}|=\left(\!\!\left({\begin{matrix}n\\k\end{matrix}}\right)\!\!\right)={\binom {n+k-1}{k}}={\frac {(n+k-1)!}{k!\cdot (n-1)!}}$

mit $n=|Z|$ und $k=|D|$.

Twelvefold way

	beliebige f	injektive f	surjektive f
$f$	$n^{k}$	$n^{\underline {k}}$	$n\cdot {\begin{Bmatrix}k\\n\end{Bmatrix}}$
$f\circ S_{k}$	${\binom {n+k-1}{k}}$	${\binom {n}{k}}$	${\binom {k-1}{k-n}}$
$S_{n}\circ f$	$\sum _{i=0}^{n}{\begin{Bmatrix}k\\i\end{Bmatrix}}$	$[k\leq n]$	${\begin{Bmatrix}k\\n\end{Bmatrix}}$
$S_{n}\circ f\circ S_{k}$	$p_{n}(n+k)$	$[k\leq n]$	$p_{n}(k)$

$f$	$f\colon D\to Z$
$n$	$n=|Z|$
$k$	$k=|D|$
$n^{\underline {k}}$	fallende Faktorielle
${\binom {n}{k}}$	Binomialkoeffizient
${\begin{Bmatrix}k\\n\end{Bmatrix}}$	Stirling-Zahl zweiter Art
$p_{n}(k)$	Anzahl der Partitionen von $k$ in genau $n$ Teile
$[A]$	Iverson-Klammern ([falsch]=0, [wahr]=1)
$S_{k}$	symmetrische Gruppe