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