Rencontres-Zahl

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Rencontres-Zahlen Dn,k
{}_{n} \! \diagdown \!\! {}^{k} 0 1 2 3 4 5 6 Summe
0 1 1
1 0 1 1
2 1 0 1 2
3 2 3 0 1 6
4 9 8 6 0 1 24
5 44 45 20 10 0 1 120
6 265 264 135 40 15 0 1 720

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 genau 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 Subfakultät, eine Formel für die Zahl möglicher fixpunktfreier Permutationen (auch 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[Bearbeiten]

Ein Autobesitzer hat den Motor seines neuen Vierzylinders geputzt und vergessen, sich zu notieren, welches der vier Zündkabel auf welche Zündkerze gehört. Wie viele Möglichkeiten gibt es, genau zwei der vier 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: (\mathbf 1,\mathbf 2,4,3), (4,\mathbf 2,\mathbf 3,1), (2,1,\mathbf 3,\mathbf 4), (\mathbf 1,3,2,\mathbf 4), (\mathbf 1,4,\mathbf 3,2), (3,\mathbf 2,1,\mathbf 4).

Ein Jahr später passiert ihm dasselbe mit dem Motor seines neuen Sechszylinders. Wie viele Möglichkeiten gibt es nun, wieder genau 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[Bearbeiten]

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

Weblinks[Bearbeiten]