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<sub>n, k</sub> 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<sub>7, 2</sub> = 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<sub>7, 2</sub> = 924 possibilities that exactly 2 previous couples meet again by chance.
Here is the beginning of this array :
The numbers in the k = 0 column enumerate derangements. Thus
for non-negative n. It turns out that
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 , we have
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 are generated by the power series ; accordingly, an explicit formula for D<sub>n, m</sub> can be derived as follows:
This immediately implies that
for n large, m fixed.
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<nowiki>!</nowiki>. If one divides all the entries in the nth row by n<nowiki>!</nowiki>, 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
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.
As the size of the permuted set grows, we get
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.