Samiksha Jaiswal (Editor)

Rencontres numbers

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

In combinatorial mathematics, 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 Dnk is the number of permutations of { 1, ..., n } that have exactly k fixed points.

Contents

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 couples, where after tea-break the participants are told to randomly find a partner to continue, and there are D7, 2 = 924 possibilities once more, now, that 2 previous couples meet again just 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 , 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 = n ! e ,

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 , we have

D n , k = ( n k ) 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 ez/(1 − z); accordingly, an explicit formula for Dnm 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 ! .

This immediately implies that

D n , m = ( n m ) D n m , 0  and  D n , m n ! 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 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 D n , k n ! = e 1 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.

References

Rencontres numbers Wikipedia


Similar Topics