Permutationen

Das Berechnen aller möglichen Permutationen von n Elementen ist eine typische Aufgabenstellung der Kombinatorik. Schon in der im 13. Jahrhundert erschienenen Schrift „De Vetula“ wurde bei der mathematischen Beantwortung der Frage, mit welchen Erfolgsaussichten auf Augenzahlen zwischen 3 und 18 beim Wurf mit drei Würfeln gesetzt werden kann, mit Permutationen gearbeitet.

Von n verschiedenen Elementen gibt es $n\cdot \left(n-1\right)\cdot \mathrm{...}\cdot 2\cdot 1$ Möglichkeiten der Anordnung. Da es sich um verschiedene Elemente handelt, spricht man auch von Permutationen ohne Wiederholung . Für die Anzahl derartiger Permutationen gilt also:
$P_n=n\cdot \left(n-1\right)\cdot \mathrm{...}\cdot 2\cdot 1=n!\left(n\in \mathbb{N}\right)$

Für $n=0$ definiert man zweckmäßigerweise $0!=1$. Da eine
n-elementige Menge nur verschiedene Objekte enthält, gibt es $n!$ Möglichkeiten, ihre Elemente anzuordnen.

Sind unter den anzuordnenden Objekten Elemente gleich, so reduziert sich die Anzahl der möglichen Permutationen.
Für die Anzahl der Permutationen von n Elementen mit Wiederholung ${}^W{P}_n$ (n Elemente, von denen je $n_1,n_2,\mathrm{...,}{n}_k$ untereinander gleich sind) gilt:
${}^W{P}_n=\frac{n!}{n_1!\cdot n_2!\cdot \mathrm{...}\cdot n_k!}\left(n\in \mathbb{N}\backslash \left\{0\right\};k<n;n_1+n_2+\mathrm{...}+n_k=n\right)$

Ein schrittweises Berechnen der Werte von $n!$ zeigt, dass die Zahlen für wachsendes n schnell sehr groß werden. Für große n kann man aber Näherungsformeln verwenden, z.B. die folgenden:
$\begin{array}{l}n!\approx n^n\cdot e^{-n}\cdot \sqrt{2\pi n}\left(\text{STIRLING-Formel}\right)\\ n!\approx n^n\cdot e^{-n}\cdot \sqrt{2\pi \left(n+\frac{1}{6}\right) } \end{array}$

Mithilfe computergestützter Simulationen kann man sich von der Güte der Näherungsformeln für verschiedene n überzeugen.

In der Rangkorrelationsanalyse, einem speziellen Teil der Korrelationsanalyse, untersucht man, inwieweit eine bestimmte Permutation zufälligen Charakter besitzt.

• Beispiel: Ein Autohersteller hat von einem Subunternehmen zwei verschiedene Sendungen des gleichen Bauteils erhalten. Er möchte nun wissen, ob man die Hypothese annehmen sollte, dass die erste Lieferung hinsichtlich eines bestimmten Parameters wesentlich kleinere Messwerte aufweist als die zweite.

Dazu werden der ersten Lieferung n und der zweiten m Bauteile „auf gut Glück“ entnommen und jeweils der interessierende Parameter gemessen. In der Reihenfolge der durchgeführten Messungen erhält man die Werte $x_1,\mathrm{...,}{x}_n,x{\text{'}}_1,\mathrm{...,}x{\text{'}}_m$.

Ordnet man die Messwerte der Größe nach, ergibt sich eine bestimmte Permutation, z.B. $x_{11},x_9,x_5,x{\text{'}}_4,\mathrm{...,}{x}_2,x{\text{'}}_9,x{\text{'}}_{12}$. Wenn dies eine „Zufallspermutation“ ist, so wäre dies ein Indiz dafür, dass sich die beiden Lieferungen hinsichtlich des untersuchten Parameters nicht wesentlich voneinander unterscheiden.

Als Maß für die Zufälligkeit einer Permutation kann man z.B. die Anzahl der sogenannten Inversionen benutzen, wobei zwei Elemente einer Permutation eine Inversion bilden, wenn ihre Anordnung im Vergleich zu „natürlichen“ umgekehrt ist, wenn also bei obiger Hypothese ein $x_i$ nach einem $x{\text{'}}_k$ steht.