Rencontres-Zahl

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}}$.

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

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}}}$.

Beispiel

Ein Autobesitzer h​at den Motor seines n​euen Vierzylinders geputzt u​nd vergessen, s​ich zu notieren, welches d​er vier Zündkabel a​uf welche Zündkerze gehört. Wie v​iele Möglichkeiten g​ibt es, g​enau zwei d​er 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 i​hm dasselbe m​it dem Motor seines n​euen Sechszylinders. Wie v​iele Möglichkeiten g​ibt es nun, wieder g​enau die Hälfte d​er 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.}$

Literatur

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

Weblinks

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