In combinatorics, the rencontres numbers are a triangular array of integers that enumerate permutations of the set { 1, ..., n } with specified numbers of fixed points: in other words, partial derangements. (Rencontre is French for encounter. By some accounts, the problem is named after a solitaire game.) For n ≥ 0 and 0 ≤ k ≤ n, the rencontres number Dn, k is the number of permutations of { 1, ..., n } that have exactly k fixed points. For example, if seven presents are given to seven different people, but only two are destined to get the right present, there are D7, 2 = 924 ways this could happen. Another often cited example is that of a dance school with 7 opposite-sex couples, where, after tea-break the participants are told to randomly find an opposite-sex partner to continue, then once more there are D7, 2 = 924 possibilities that exactly 2 previous couples meet again by chance.
Numerical values Here is the beginning of this array (sequence A008290 in the OEIS):
Formulas The numbers in the k = 0 column enumerate derangements. Thus
D 0 , 0 = 1 , {\displaystyle D_{0,0}=1,\!}
D 1 , 0 = 0 , {\displaystyle D_{1,0}=0,\!}
D n + 2 , 0 = ( n + 1 ) ( D n + 1 , 0 + D n , 0 ) {\displaystyle D_{n+2,0}=(n+1)(D_{n+1,0}+D_{n,0})\!}
for non-negative n. It turns out that
D n , 0 = ⌈ n ! e ⌋ , {\displaystyle D_{n,0}=\left\lceil {\frac {n!}{e}}\right\rfloor ,}
where the ratio is rounded up for even n and rounded down for odd n. For n ≥ 1, this gives the nearest integer. More generally, for any k ≥ 0 {\displaystyle k\geq 0} , we have
D n , k = ( n k ) ⋅ D n − k , 0 . {\displaystyle D_{n,k}={n \choose k}\cdot D_{n-k,0}.}
The proof is easy after one knows how to enumerate derangements: choose the k fixed points out of n; then choose the derangement of the other n − k points. The numbers Dn,0/(n!) are generated by the power series e−z/(1 − z); accordingly, an explicit formula for Dn, m can be derived as follows:
D n , m = n ! m ! [ z n − m ] e − z 1 − z = n ! m ! ∑ k = 0 n − m ( − 1 ) k k ! . {\displaystyle D_{n,m}={\frac {n!}{m!}}[z^{n-m}]{\frac {e^{-z}}{1-z}}={\frac {n!}{m!}}\sum _{k=0}^{n-m}{\frac {(-1)^{k}}{k!}}.}
This immediately implies that
D n , m = ( n m ) D n − m , 0 and D n , m n ! ≈ e − 1 m ! {\displaystyle D_{n,m}={n \choose m}D_{n-m,0}\;\;{\mbox{ and }}\;\;{\frac {D_{n,m}}{n!}}\approx {\frac {e^{-1}}{m!}}}
for n large, m fixed.
Probability distribution The sum of the entries in each row for the table in "Numerical Values" is the total number of permutations of { 1, ..., n }, and is therefore n!. If one divides all the entries in the nth row by n!, one gets the probability distribution of the number of fixed points of a uniformly distributed random permutation of { 1, ..., n }. The probability that the number of fixed points is k is
… excerpt ends here. Continue reading the full article.
