Derangement

Zahl der Permutationen und Derangements (totalen Versetzungen) von n Elementen. P(n) - n-Permutationen; D(n) - totale Derangements (bei der alle n Elemente ihre Plätze wechseln).

In der Kombinatorik versteht man unter einem Derangement eine sogenannte fixpunktfreie Permutation oder „totale Versetzung“, d.h. eine Vertauschung von Elementen, bei der keines von ihnen seine Ausgangsposition beibehält.

Für solche Permutationen $\sigma\colon\left\lbrace 1, \ldots, n\right\rbrace\to\left\lbrace 1,\ldots, n \right\rbrace$ gilt dann stets $\sigma\left(i\right)\ne i$.

Die Anzahl möglicher Derangements einer n-elementigen Menge errechnet sich mit Hilfe der Subfakultät !n:

$!n = n! \cdot\sum_{i=0}^n {\left(-1\right)^i \over i!}.$

Sollen dagegen k der n Elemente an ihrem alten Platz verbleiben, spricht man von unvollständigen oder partiellen Derangements, deren mögliche Anzahl als Rencontres-Zahl bezeichnet wird. Die Subfakultät !n ist also der Spezialfall einer Rencontres-Zahl für k = 0.

Beispiel

Die beiden möglichen Derangements von {1,2,3} sind in Tupelschreibweise die Anordnungen (2,3,1) und (3,1,2).

Literatur

• Julian Havil: Verblüfft?! Mathematische Beweise unglaublicher Ideen. Springer, 2009, ISBN 978-3-540-78235-3, S. 45–58