Rencontres number

Rencontres numbers D _{n , k}

${\displaystyle {}_{n}\!\diagdown \!\!{}^{k}}$	0	1	2	3	4th	5	6th	total
0	1							1
1	0	1						1
2	1	0	1					2
3	2	3	0	1				6th
4th	9	8th	6th	0	1			24
5	44	45	20th	10	0	1		120
6th	265	264	135	40	15th	0	1	720

In combinatorics , a Rencontres number ( French: encounters ) is the number of permutations of a set of distinguishable elements designated with, in which elements exactly retain their original place or “find” again purely by chance: ${\displaystyle D_{n,k}}$ ${\displaystyle n}$ ${\displaystyle k}$

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

In the event that none of the elements retains its place and "finds", arises as a special case, the Subfakultät , a formula for the number of possible fixed point free permutations (also derangements or "Total transfers") of elements in which so none of them at remains in its previous place: ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle (k=0)}$

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

example

A car owner cleaned the engine of his new four-cylinder and forgot to make a note of which of the four ignition cables goes on which spark plug. How many ways are there to reconnect exactly two of the four cables?

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

In 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} )}$

A year later, the same thing happened to him with the engine of his new six-cylinder. How many possibilities are there to put exactly half of the ignition cables back on?

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

literature

• Dieter J. saddle roof: biomathematics I . Akademie-Verlag Berlin, 1971, ISBN 3-528-06083-2 , pp. 37-40.

Web links

• Eric W. Weisstein : Partial Derangement . In: MathWorld (English).
• Follow A008290 in OEIS