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

This article is issued from Wikibooks. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.