Direkt zum Inhalt

Lexikon der Mathematik: Derangement

fixpunktfreie Permutation.

Sei Sn die Menge der Permutationen auf ℕn = { 1, 2, …, n} und mp(n) die Anzahl der Permutationen fSn, welche genau p Fixpunkte i haben.

Sei Ai :={ fSn, f(i) = i}. Für alle A ⊆ Nn gilt offensichtlich \begin{eqnarray}|\displaystyle \mathop{\cap }\limits_{i\in A}{A}_{i}|=(n-|A|)!.\end{eqnarray}

Somit ist \begin{eqnarray}{m}_{p}(n)=\frac{n!}{p!}\displaystyle \sum _{k=0}^{n-k}\frac{{(-1)}^{k}}{k!}.\end{eqnarray}

Insbesondere ist die Anzahl der fixpunktfreien Permutationen, also der Derangements, \begin{eqnarray}{D}_{n}={m}_{0}(n)=n!\displaystyle \sum _{k=0}^{n}\frac{{(-1)}^{k}}{k!}.\end{eqnarray}

Daraus folgt, daß lim \begin{eqnarray}\mathop{\mathrm{lim}}\limits_{x\to \infty }\frac{{D}_{n}}{n!}=\frac{1}{\text{e}}.\end{eqnarray}

Die Formel \begin{eqnarray}{m}_{p}(n)=\left(\begin{array}{c}n\\ p\end{array}\right){m}_{0}(n-p)\end{eqnarray} gibt die Rekursion für die Zahlen mp(n) an.

Als Beispiel betrachten wir ein Manuskript mit n Seiten. Angenommen, daß durch einen Windstoß die Seiten aufgewirbelt und nach Belieben wieder geordnet werden. Wie groß ist die Wahrscheinlichkeit, daß nicht eine einzige Seite an ihrem richtigen Platz liegt? Für große n ergibt die obige Formel einen Wert größer als 1/3.

Schreiben Sie uns!

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnerinhalte

Bitte erlauben Sie Javascript, um die volle Funktionalität von Spektrum.de zu erhalten.