This site is supported by donations to The OEIS Foundation.

Rencontres numbers

From OeisWiki
(Redirected from Number of partial derangements)
Jump to: navigation, search

The rencontres numbers (partial derangement numbers) are the number of partial derangements, or number of permutations with r rencontres[1] of distinct objects (i.e. the number of permutations of distinct objects with fixed points).

For and the rencontres number is the number of permutations of that have exactly fixed points.

The number of permutations with 0 rencontres (number of complete derangements) are the number of derangements .

Triangle of rencontres numbers

The terms of the th trivial, i.e. , falling diagonals from the right (indexed from 0,) where , are

  • the number of permutations of n with n-1 rencontres (i.e. ) is obviously 0, since once you reach rencontres, you necessarily have rencontres.

The triangle shows that the first two columns have the relations

(obviously, since there are ways to choose the fixed point)
(since see number of derangements (recurrences))

giving


Rencontres numbers
= 0 1
1 0 1
2 1 0 1
3 2 3 0 1
4 9 8 6 0 1
5 44 45 20 10 0 1
6 265 264 135 40 15 0 1
7 1854 1855 924 315 70 21 0 1
8 14833 14832 7420 2464 630 112 28 0 1
9 133496 133497 66744 22260 5544 1134 168 36 0 1
10 1334961 1334960 667485 222480 55650 11088 1890 240 45 0 1
11 14684570 14684571 7342280 2447445 611820 122430 20328 2970 330 55 0 1
12 176214841 176214840 88107426 29369120 7342335 1468368 244860 34848 4455 440 66 0 1
= 0 1 2 3 4 5 6 7 8 9 10 11 12


The triangle of rencontres numbers gives the infinite sequence of finite sequences

{{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}, {14833, 14832, 7420, 2464, 630, 112, 28, 0, 1}, {133496, 133497, 66744, 22260, 5544, 1134, 168, 36, 0, 1}, ...}

Triangle of rencontres numbers (number of permutations of elements with fixed points). (Cf. A008290)

{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, 14833, 14832, 7420, 2464, 630, 112, 28, 0, 1, 133496, 133497, 66744, 22260, 5544, 1134, 168, 36, 0, 1, ...}

Triangle of D_{n, r} / D_{n−r, 0}

The following triangle reveals that the terms of the th nontrivial, i.e. , falling diagonal from the right (indexed from 0,) where , are divisible by the leftmost term of the falling diagonal.

Furthermore, the subtriangle excluding the rightmost two (trivial) falling diagonals (i.e. for ) is now the corresponding subtriangle of the Pascal triangle, thus we have

This is obvious since there are ways to choose the fixed objects and the remaining objects must be a complete derangement.


= 0 1
1 0 1
2 1 0 1
3 1 3 0 1
4 1 4 6 0 1
5 1 5 10 10 0 1
6 1 6 15 20 15 0 1
7 1 7 21 35 35 21 0 1
8 1 8 28 56 70 56 28 0 1
9 1 9 36 84 126 126 84 36 0 1
10 1 10 45 120 210 252 210 120 45 0 1
11 1 11 55 165 330 462 462 330 165 55 0 1
12 1 12 66 220 495 792 924 792 495 220 66 0 1
= 0 1 2 3 4 5 6 7 8 9 10 11 12


Formulae

The number of derangements of a nonempty set may be obtained from the ratio of the factorial of and Euler's number

where the ratio is rounded up for even and rounded down for odd .

The number of permutations with r rencontres (number of permutations with n-r derangements) is given by

The proof is easy after one knows how to enumerate derangements: choose the fixed points out of ; then choose the derangement of the other points.

An explicit formula for can be derived as follows

This immediately implies that

for large, fixed.

Examples

Recurrences

The numbers in the column are the number of derangements (number of permutations with 0 rencontres or number of permutations of n with n derangements.) Thus

Other formulae

Generating function

Ordinary generating function

O.g.f. for column is [TO BE VERIFIED]

O.g.f. for row is

Exponential generating function

[TO BE VERIFIED]

E.g.f. for triangle of rencontres numbers is

Asymptotic behaviour

Permutations having at least r fixed points

Permutations having at most r fixed points

Sequences

See also

Notes

  1. "Rencontre" being a french word meaning encounter.