# Rencontres numbers

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 D$_{n,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 D$_{7,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 D$_{7,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):
| kn | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 0 | 1 | | | | | | | | |
| 1 | 0 | 1 | | | | | | | |
| 2 | 1 | 0 | 1 | | | | | | |
| 3 | 2 | 3 | 0 | 1 | | | | | |
| 4 | 9 | 8 | 6 | 0 | 1 | | | | |
| 5 | 44 | 45 | 20 | 10 | 0 | 1 | | | |
| 6 | 265 | 264 | 135 | 40 | 15 | 0 | 1 | | |
| 7 | 1854 | 1855 | 924 | 315 | 70 | 21 | 0 | 1 | |
| 8 | 14833 | 14832 | 7420 | 2464 | 630 | 112 | 28 | 0 | 1 |
ordered by number of moved elements :
The usual way (table above) to show the rencontres numbers is in columns corresponding to the number of fixed points $k$.
But one can also order them in columns corresponding to the number of moved elements $i=n-k$ (sequence A098825 in the OEIS).
Each entry in the table below on the left can be factored into two terms given in the table below on the right: the product of a binomial coefficient (given first in red) and a subfactorial (given second in blue).
In this order each column corresponds to one subfactorial: $~~~T(n,i)={\binom {n}{i}}~\cdot ~!i$ :
| in | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 0 | 1 | | | | | | | | |
| 1 | 1 | 0 | | | | | | | |
| 2 | 1 | 0 | 1 | | | | | | |
| 3 | 1 | 0 | 3 | 2 | | | | | |
| 4 | 1 | 0 | 6 | 8 | 9 | | | | |
| 5 | 1 | 0 | 10 | 20 | 45 | 44 | | | |
| 6 | 1 | 0 | 15 | 40 | 135 | 264 | 265 | | |
| 7 | 1 | 0 | 21 | 70 | 315 | 924 | 1855 | 1854 | |
| 8 | 1 | 0 | 28 | 112 | 630 | 2464 | 7420 | 14832 | 14833 |
| in | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 0 | 1⋅1 | | | | | | | | |
| 1 | 1⋅1 | 1⋅0 | | | | | | | |
| 2 | 1⋅1 | 2⋅0 | 1⋅1 | | | | | | |
| 3 | 1⋅1 | 3⋅0 | 3⋅1 | 1⋅2 | | | | | |
| 4 | 1⋅1 | 4⋅0 | 6⋅1 | 4⋅2 | 1⋅9 | | | | |
| 5 | 1⋅1 | 5⋅0 | 10⋅1 | 10⋅2 | 5⋅9 | 1⋅44 | | | |
| 6 | 1⋅1 | 6⋅0 | 15⋅1 | 20⋅2 | 15⋅9 | 6⋅44 | 1⋅265 | | |
| 7 | 1⋅1 | 7⋅0 | 21⋅1 | 35⋅2 | 35⋅9 | 21⋅44 | 7⋅265 | 1⋅1854 | |
| 8 | 1⋅1 | 8⋅0 | 28⋅1 | 56⋅2 | 70⋅9 | 56⋅44 | 28⋅265 | 8⋅1854 | 1⋅14833 |

## Formulas

The numbers in the k = 0 column enumerate derangements. Thus
    $D_{0,0}=1,\!$
    $D_{1,0}=0,\!$
    $D_{n+2,0}=(n+1)(D_{n+1,0}+D_{n,0})\!$
for non-negative n. It turns out that
    $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\geq 0$, we have
    $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 D$_{n,0}$/(n!) are generated by the power series e$^{−z}$/(1 − z); accordingly, an explicit formula for D$_{n,m}$ can be derived as follows:
    $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 \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
    ${D_{n,k} \over n!}.$
For n ≥ 1, the expected number of fixed points is 1 (a fact that follows from linearity of expectation).
More generally, for i ≤ n, the ith moment of this probability distribution is the ith moment of the Poisson distribution with expected value 1. For i > n, the ith moment is smaller than that of that Poisson distribution. Specifically, for i ≤ n, the ith moment is the ith Bell number, i.e. the number of partitions of a set of size i.

### Limiting probability distribution

As the size of the permuted set grows, we get
    $\lim _{n\to \infty }{D_{n,k} \over n!}={e^{-1} \over k!}.$
This is just the probability that a Poisson-distributed random variable with expected value 1 is equal to k. In other words, as n grows, the probability distribution of the number of fixed points of a random permutation of a set of size n approaches the Poisson distribution with expected value 1.