fixpunktfreie Permutation.

Sei S_n die Menge der Permutationen auf ℕ_n = { 1, 2, …, n} und m_p(n) die Anzahl der Permutationen f ∈ S_n, welche genau p Fixpunkte i haben.

Sei A_i :={ f ∈ S_n, f(i) = i}. Für alle A ⊆ N_n 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 m_p(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.