Rencontres numbers

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:

:egin{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 & ddotsend{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} 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


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Derangement — For the psychological condition, see psychosis. Number of possible permutations and derangements of n elements. P(n) is the number of n permutations; D(n) is the number of derangements (n permutations where all of the n elements change their… …   Wikipedia

  • Permutation — For other uses, see Permutation (disambiguation). The 6 permutations of 3 balls In mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting (rearranging) objects or values.… …   Wikipedia

  • Random permutation statistics — The statistics of random permutations, such as the cycle structure of a random permutation are of fundamental importance in the analysis of algorithms, especially of sorting algorithms, which operate on random permutations. Suppose, for example,… …   Wikipedia

  • Triangular array — Not to be confused with Triangular matrix. The triangular array whose right hand diagonal sequence consists of Bell numbers In mathematics and computing, a triangular array of numbers, polynomials, or the like, is a doubly indexed sequence in… …   Wikipedia

  • List of combinatorics topics — This is a list of combinatorics topics.A few decades ago it might have been said that combinatorics is little more than a way to classify poorly understood problems, and some standard remedies. Great progress has been made since 1960.This page is …   Wikipedia

  • List of statistics topics — Please add any Wikipedia articles related to statistics that are not already on this list.The Related changes link in the margin of this page (below search) leads to a list of the most recent changes to the articles listed below. To see the most… …   Wikipedia

  • Schuette–Nesbitt formula — In probability theory, the Schuette–Nesbitt formula is a generalization of the probabilistic version of the inclusion exclusion principle. It is named after Donald R. Schuette and Cecil J. Nesbitt. The Schuette–Nesbitt formula has practical… …   Wikipedia

  • List of mathematics articles (R) — NOTOC R R. A. Fisher Lectureship Rabdology Rabin automaton Rabin signature algorithm Rabinovich Fabrikant equations Rabinowitsch trick Racah polynomials Racah W coefficient Racetrack (game) Racks and quandles Radar chart Rademacher complexity… …   Wikipedia

  • List of triangle topics — This list of triangle topics includes things related to the geometric shape, either abstractly, as in idealizations studied by geometers, or in triangular arrays such as Pascal s triangle or triangular matrices, or concretely in physical space.… …   Wikipedia

  • Random permutation — A random permutation is a random ordering of a set of objects, that is, a permutation valued random variable. The use of random permutations is often fundamental to fields that use randomized algorithms. Such fields include coding theory,… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”