Formelsammlung Mathematik: Elementare Kombinatorik

Permutationen

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

Eine Abbildung $\pi \in \mathrm{B}\mathrm{i}\mathrm{j}(M,M)$ heißt Permutation. Es gilt die Gruppenisomorphie $\mathrm{B}\mathrm{i}\mathrm{j}(M,M)\simeq S_n$.

Anzahl der Permutationen:

$|\mathrm{B}\mathrm{i}\mathrm{j}(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 \dots \cdot (n-1)\cdot n.$

Variationen

Variationen ohne Wiederholung

Sei $\mathrm{I}\mathrm{n}\mathrm{j}(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{I}\mathrm{n}\mathrm{j}(D,Z)|=n^{\underset{\_}{k}}=\frac{n!}{(n-k)!}=k!\cdot (\genfrac{}{}{0ex}{}{n}{k}).$

Variationen mit Wiederholung

Sei $\mathrm{A}\mathrm{b}\mathrm{b}(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{A}\mathrm{b}\mathrm{b}(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:⟺\mathrm{\exists }\pi \in S_k: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{I}\mathrm{n}\mathrm{j}(D,Z)\}|=(\genfrac{}{}{0ex}{}{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{A}\mathrm{b}\mathrm{b}(D,Z)\}|=\left(\left(\begin{array}{c}n\\ k\end{array}\right)\right)=(\genfrac{}{}{0ex}{}{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^{\underset{\_}{k}}$	$n\cdot \left\{\begin{array}{c}k\\ n\end{array}\right\}$
$f\circ S_k$	$(\genfrac{}{}{0ex}{}{n+k-1}{k})$	$(\genfrac{}{}{0ex}{}{n}{k})$	$(\genfrac{}{}{0ex}{}{k-1}{k-n})$
$S_n\circ f$	$\sum _{i=0}^n\left\{\begin{array}{c}k\\ i\end{array}\right\}$	$[k\le n]$	$\left\{\begin{array}{c}k\\ n\end{array}\right\}$
$S_n\circ f\circ S_k$	$p_n(n+k)$	$[k\le n]$	$p_n(k)$

$f$	$f:D\to Z$
$n$	$n=|Z|$
$k$	$k=|D|$
$n^{\underset{\_}{k}}$	fallende Faktorielle
$(\genfrac{}{}{0ex}{}{n}{k})$	Binomialkoeffizient
$\left\{\begin{array}{c}k\\ n\end{array}\right\}$	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