Rencontres-Zahl

In der Kombinatorik versteht man unter einer Rencontres-Zahl (französisch Begegnungen) die mit D(n;k) bezeichnete Anzahl der Permutationen einer Menge n unterscheidbarer Elemente, bei der k Elemente ihren ursprünglichen Platz beibehalten bzw. rein zufällig „wiederfinden“:

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

Für den Fall, dass keines der n Elemente seinen Platz beibehält bzw. „wiederfindet“, ergibt sich als Sonderfall die Formel für die Zahl möglicher Derangements oder „Totalversetzungen“ der n Elemente, bei denen also keines von ihnen (k = 0) an seinem bisherigen Platz bleibt:

$D(n;0) = \, !n = n! \cdot\sum_{i=0}^n {\left(-1\right)^i \over i!}\quad\text{mit}\quad\lim_{n \to \infty}\ \sum_{i=0}^n {\left(-1\right)^i \over i!} = \frac1 e.$

Beispiel

Ein Autobesitzer hat den Motor seines neuen Vierzylinders geputzt und vergessen, sich zu notieren, welches der 4 Zündkabel auf welche Zündkerze gehört. Wie viele Möglichkeiten gibt es, rein zufällig 2 der 4 Kabel wieder richtig aufzustecken?

$D(4;2) = \frac {4!}{2!} \cdot \left({\left(-1\right)^0 \over 0!} + {\left(-1\right)^1 \over 1!} + {\left(-1\right)^2 \over 2!}\right) = 6.$

Im Detail: (1,2,4,3), (4,2,3,1), (2,1,3,4), (1,3,2,4), (1,4,3,2), (3,2,1,4).

Ein Jahr später passiert ihm dasselbe mit dem Motor seines neuen Sechszylinders. Wie viele Möglichkeiten gibt es nun, rein zufällig wieder die Hälfte der Zündkabel richtig aufzustecken?

$D(6;3) = \frac {6!}{3!} \cdot \left({\left(-1\right)^0 \over 0!} + {\left(-1\right)^1 \over 1!} + {\left(-1\right)^2 \over 2!} + {\left(-1\right)^3 \over 3!}\right) = 40.$

Literatur

• Dieter J. Schadach: Biomathematik I; Akademie-Verlag Berlin, 1971, ISBN 3-528-06083-2, S.37-40.