This site is supported by donations to The OEIS Foundation.

Number of derangements

From OeisWiki
Jump to: navigation, search


This article needs more work.

Please help by expanding it!


The number of (complete) derangements, or number of permutations with no rencontres[1] of distinct objects (i.e. the number of permutations of distinct objects with no fixed point) is given by the subfactorial of . The derangement numbers are given by the subfactorial numbers.

Formula

Subfactorial numbers

A000166 Subfactorial or rencontres numbers,[2] or derangements: number of permutations of n elements with no fixed points.

{1, 0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961, 14684570, 176214841, 2290792932, 32071101049, 481066515734, 7697064251745, 130850092279664, 2355301661033953, ...}

The last digit (base 10) of seems to follow the pattern (of length 10)

{1, 0, 1, 2, 9, 4, 5, 4, 3, 6}

Example

You have 6 balls in 6 different colors, and for every ball you have a box of the same color. How many derangements do you have, if no ball is in a box of the same color?

.

Comparison of derangement, permutation and arrangement numbers

Comparison of derangement, permutation and arrangement numbers
Number of derangements

Number of permutations

Number of arrangements

0 1 1 1
1 0 1 2
2 1 2 5
3 2 6 16
4 9 24 65
5 44 120 326
6 265 720 1957
7 1854 5040 13700
8 14833 40320 109601
9 133496 362880 986410
10 1334961 3628800 9864101
11 14684570 39916800 108505112
12 176214841 479001600 1302061345
13 2290792932 6227020800 16926797486
14 32071101049 87178291200 236975164805
15 481066515734 1307674368000 3554627472076
16 7697064251745 20922789888000 56874039553217
17 130850092279664 355687428096000 966858672404690
18 2355301661033953 6402373705728000 17403456103284421
19 44750731559645106 121645100408832000 330665665962404000
20 895014631192902121 2432902008176640000 6613313319248080001

Recurrences

Note that the factorial has a similar recurrence

So, for

Other formulae

where (Cf. A001113) is Euler's number and is the incomplete gamma function.

A very good approximation is given by

If rounded, you get a perfect formula for

If you add 1 to the factorial, before dividing, you can truncate instead of rounding to get a perfect formula for

Comparison with approximations
0 1 0,3679 0 0,7358 0
1 0 0,3679 0 0,7358 0
2 1 0,7358 1 1,1036 1
3 2 2,2073 2 2,5752 2
4 9 8,8291 9 9,1970 9
5 44 44,1455 44 44,5134 44
6 265 264,8732 265 265,2411 265
7 1854 1854,1124 1854 1854,4803 1854
8 14833 14832,8991 14833 14833,2669 14833
9 133496 133496,0916 133496 133496,4595 133496

where is the round function and is the floor function.

There is a sequence (Cf. A000255) with the members , and the recursive rule:

With this sequence you can calculate the subfactorial

1 0 1 2 9 44 265 1854 14833 133496 1334961
0 1 2 3 4 5 6 7 8 9 10
1 1 3 11 53 309 2119 16687 148329 1468457 16019531

Generating function

Ordinary generating function

where is the exponential integral.

Exponential generating function

Asymptotic behaviour

The limit of the quotient of factorial and subfactorial converges to (Cf. A001113 and Euler's number)

Proof:

The limit of the quotient of the number of arrangements of any subset of distinct objects over the number of derangements of distinct objects converges to (Cf. A072334)

The geometric mean of the number of arrangements and the number of derangements is asymptotic to the number of permutations

Permutations having at least one fixed point

The number of permutations having at least one fixed point, thus not being (complete) derangements is given by

where the second summation gives the empty sum (defined as the additive identity, i.e. 0) for .

Sequences

The subfactorial numbers (or rencontres numbers, or derangements: number of permutations of elements with no fixed points) (Cf. A000166) are

{1, 0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961, 14684570, 176214841, 2290792932, 32071101049, 481066515734, 7697064251745, 130850092279664, 2355301661033953, ...}

(Cf. A000255) gives

{1, 1, 3, 11, 53, 309, 2119, 16687, 148329, 1468457, 16019531, 190899411, 2467007773, 34361893981, 513137616783, 8178130767479, 138547156531409, 2486151753313617, ...}

The number of permutations of , having a fixed point (Cf. A002467) are

{0, 1, 1, 4, 15, 76, 455, 3186, 25487, 229384, 2293839, 25232230, 302786759, 3936227868, 55107190151, 826607852266, 13225725636255, 224837335816336, 4047072044694047, ...}

See also



Notes

  1. "Rencontre" being a french word meaning encounter.
  2. Number of permutations with 0 rencontres, i.e. number of permutations with 0 fixed points.

References