Rencontres numbers

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 :$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\}\; ight]$

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

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 "n"th 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 "i"th moment of this probability distribution is the "i"th Bell number, i.e., the number of partitions of a set of size "i". This is the same as the "i"th moment of a Poisson distribution with expected value 1. For "i" > "n", the "i"th moment is smaller than that of that Poisson distribution.

Limiting probability distribution

As the size of the permuted set grows, we get

:$lim\_\{n\; oinfty\}\; \{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.

References

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

External links

* [http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A008290 Entry for rencontres numbers] at the On-Line Encyclopedia of Integer Sequences