Kombinatorik

From bio-physics-wiki

Jump to: navigation, search

Permutation

Wie viele Möglichkeiten gibt es $3$ Bücher (a,b,c) in einem Regal anzuordnen?

\begin{align} abc\\ bca\\ cab\\ acb\\ bac\\ cba\\ \vdots \hspace{0.25cm}\\ \end{align}

Jede einzelne dieser Anordnungen ist eine Permutation der $3$ Bücher.

Für $n$ Elemente gibt es $n!=n \cdot (n-1) \cdot (n-2) \cdot (n-3) \dots 3 \cdot 2 \cdot 1$ Permutationen

Permutation von klassenweise äquivalenten Objekten

Für die Zahl der möglichen Anordnungen von Objekten aus mehreren Klassen, die untereinander jeweils innerhalb einer Klasse nicht unterscheidbar sind, ist es hilfreich, zunächst die mögliche Zahl der Anordnungen der Objekte zu betrachten und dann zu überlegen, wie viele dieser Anordnungen nicht unterscheidbar sind. Die Zahl der möglichen Anordnungen bei unterscheidbaren Objekten wird durch die Zahl der nicht unterscheidbaren Anordnungen geteilt.

Anzahl der Permutationen von \(n\) Elementen, die in \(k\) Gruppen von je \(l_1, l_2, \ldots, l_k\) gleichen Elementen mit \(\textstyle\sum^k_{i=1} l_i = n\) fallen

\begin{equation} \frac{n!}{l_1! \cdot l_2! \cdot \ldots \cdot l_k!} \end{equation}

Beispiele

  • Wie viele Möglichkeiten gibt es die Buchstaben $A,H,A$ anzuordnen?
Nehmen wir erst an wir unterscheiden zwischen $A_1$ und $A_2$, dann gäbe es $3!$ Permutationen
\begin{equation} \underbrace{HA_1A_2}_{a}, \hspace{1cm} \underbrace{A_1HA_2}_{b}, \hspace{1cm} \underbrace{A_1A_2H}_{c}, \hspace{1cm} \underbrace{HA_2A_1}_{d}, \hspace{1cm} \underbrace{A_2HA_1}_{e}, \hspace{1cm} \underbrace{A_2A_1H}_{f} \end{equation}
Unterscheidet man aber nicht zwischen $A_1$ und $A_2$, so ist $a=d$, $b=e$, $c=f$. Es gibt dann also nur noch $3=3!/2!$ unterscheidbare Anordnungen.
entnommen aus: Dill $\&$ Bromberg - Molecular Driving Forces - Statistical Thermodynamics in Biology, Chemistry, Physics and Nanoscience
  • Aus dem Wort „Banane“ lassen sich durch umordnen insgesamt \(\frac{6!}{2!2!1!1!} = 180\) Wörter bilden.

Kombination

(Ziehen ohne Zurücklegen; Reihenfolge ohne Bedeutung) Wie viele Möglichkeiten gibt es aus $7$ Personen $3$ Personen auszuwählen, wenn die Reihenfolge der Auswahl balanglos ist, d.h. die Stichproben {a,b,c} und ihre Permutationen {b,a,c}, {b,c,a} usw. als gleich betrachtet werden?

Für die erste Auswahl stehen $7$ Personen zur Verfügung, für die zweite Auswahl $6$ und für die dritte $5$. Das würde $7 \cdot 6 \cdot 5=210$ Möglichkeiten ergeben, davon unerscheiden sich aber $3!$ Auswahlen nur durch die Reihenfolge. Die Anzahl der möglichen Kombinationen ist daher \begin{equation} \frac{7 \cdot 6 \cdot 5}{3 \cdot 2 \cdot 1}=35 \end{equation}

Allgemein gibt es für eine Auswahl von $k$ Elementen aus insgesamt $n$ Elementen $\frac{n!}{n-k!}$ mögliche Anordnungen wobei sich $k!$ Anordnungen nur in der Reihenfolge unterscheiden sodass wir allgemein den Binomialkoeffizienten erhalten

\begin{equation}
 \begin{pmatrix} n \\ k \end{pmatrix} = \frac{n!}{k!(n-k)!}
 \end{equation}