From Wikipedia, the free encyclopedia

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. (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. See Riordan, pages 57-58 on the "problème des rencontres" and the table on page 65.

Here is the beginning of this array:

The numbers in the leftmost vertical column enumerate derangements. Thus

for non-negative n. It turns out that

where the ratio is rounded up for even n and and rounded down for odd n. For n ≥ 1, this gives the nearest integer. More generally, 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.

Contents 1 A probability distribution 2 Limiting probability distribution 3 Reference 4 External links

The sum of the entries in each row is the whole 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

For i ≤ n, the ith moment of this probability distribution is the ith Bell number, i.e., the number of partitions of a set of size i. This is the same as the ith moment of a Poisson distribution with expected value 1. For i > n, the ith moment is smaller than that of that Poisson distribution.

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.

• Riordan, John, An Introduction to Combinatorial Analysis, New York, Wiley, 1958

• Entry for rencontres numbers at the On-Line Encyclopedia of Integer Sequences