This site is supported by donations to The OEIS Foundation.
Number of derangements
From OeisWiki
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.
Contents |
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
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
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
- Number of derangements (number of complete derangements) (given by the subfactorial, recognized term)
- Number of arrangements (given by the supfactorial, suggested term, since superfactorial refers to another concept)
Notes
- ↑ "Rencontre" being a french word meaning encounter.
- ↑ Number of permutations with 0 rencontres, i.e. number of permutations with 0 fixed points.
References
- Mehdi Hassani, Derangements and Applications, Journal of Integer Sequences, 6(1), Article 03.1.2, 2003.
- Weisstein, Eric W., Derangement, from MathWorld—A Wolfram Web Resource. [http://mathworld.wolfram.com/Derangement.html], as of 2010-12-19.
- Weisstein, Eric W., Subfactorial, from MathWorld—A Wolfram Web Resource. [http://mathworld.wolfram.com/Subfactorial.html], as of 2010-12-19.