Rencontres numbers

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:

$\begin{matrix} 1 \\ 0 & 1 \\ 1 & 0 & 1 \\ 2 & 3 & 0 & 1 \\ 9 & 8 & 6 & 0 & 1 \\ 44 & 45 & 20 & 10 & 0 & 1 \\ 265 & 264 & 135 & 40 & 15 & 0 & 1 \\ 1854 & 1855 & 924 & 315 & 70 & 21 & 0 & 1 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \end{matrix}$

The numbers in the leftmost vertical 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[{n! \over e}\right]$

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

$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.

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

[edit] A probability distribution

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

${D_{n,k} \over n!}.$

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.

[edit] 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.