Rencontres-Zahl

Rencontres-Zahlen D_n,k

${\displaystyle {}_{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 ${\displaystyle D_{n,k}}$ bezeichnete Anzahl der Permutationen einer Menge ${\displaystyle n}$ unterscheidbarer Elemente, bei der genau ${\displaystyle k}$ Elemente ihren ursprünglichen Platz beibehalten bzw. rein zufällig „wiederfinden“:

${\displaystyle 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 ${\displaystyle 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 ${\displaystyle n}$ Elemente, bei denen also keines von ihnen ${\displaystyle (k=0)}$ an seinem bisherigen Platz bleibt:

${\displaystyle 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!}={\frac {1}{e}}}$.

Ein Autobesitzer hat den Motor seines 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?

${\displaystyle 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: ${\displaystyle (\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?

${\displaystyle 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.}$

• Fachredaktion des Bibliographischen Instituts (Hrsg.): Duden Rechnen und Mathematik: Das Lexikon für Schule und Praxis. Bearbeitet von Prof. Dr. Harald Scheid. 4. Auflage. Bibliographisches Institut, Mannheim, Wien, Zürich 1985, S. 540. 
• Heinz-Richard Halder, Werner Heise: Einführung in die Kombinatorik. Mit einem Anhang über formale Potenzreihen (= Mathematische Grundlagen für Mathematiker, Physiker und Ingenieure). Hanser Verlag, München, Wien 1976, ISBN 3-446-12140-4 (zbMATH Open). 
• Dieter J. Schadach: Biomathematik I. Kombinatorik, Wahrscheinlichkeit und Information (= Wissenschaftliche Taschenbücher. Band 83). Akademie-Verlag, Berlin 1971, ISBN 3-528-06083-2, S. 37–40 (zbMATH Open). 

• Eric W. Weisstein: Partial Derangement. In: MathWorld (englisch).
• Folge A008290 in OEIS