Number of derangements

This article needs more work.

Please help by expanding it!

The number of (complete) derangements, or number of permutations with no rencontre, of

n

distinct objects (i.e. the number of permutations of

n

distinct objects with no fixed point) is given by the subfactorial

!n

of

n

. The derangement numbers are given by the subfactorial numbers.

Formula

!n  :=  n! 1 − 1 1! + 1 2! − 1 3! + ⋯ + (−1) n 1 n!  =  n!   n ∑   k  = 0    (−1) k k ! .

Subfactorial numbers

A000166 Subfactorial (rencontres numbers), or derangements: number of permutations of

n

elements with no fixed point.

{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

!n, n   ≥   0,

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?

!6  =  6! ⋅  1 − 1 1! + 1 2! − 1 3! + 1 4! − 1 5! + 1 6!  =  265.

Comparison of derangement, permutation and arrangement numbers

Comparison of derangement, permutation and arrangement numbers

n Number of derangements dn = n!   n ∑   k  = 0    ( − 1) k k ! dn   ≈   n! e dn = n! e = n! e + 1 2 , n   ≥   1 Number of permutations n! n!   ≈   2√  dn an Number of arrangements an = n!   n ∑   k  = 0    1 k ! an   ≈   e n! an = e n! , n   ≥   1 A000166 A000142 A000522 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

n (n! ) 2 (n! ) 2   ∼   dn an dn an (n! ) 2  −  dn an A001044 A??????  (Add to OEIS?.)  A??????  (Add to OEIS?.)  0 1 1 0 1 1 0 1 2 4 5 − 1 3 36 32 4 4 576 585 − 9 5 14400 14344 56 6 518400 518605 − 205 7 25401600 25399800 1800 8 1625702400 9 131681894400 10 13168189440000 11 1593350922240000 12 229442532802560000 13 38775788043632640000 14 7600054456551997440000 15 1710012252724199424000000 16 437763136697395052544000000 17 126513546505547170185216000000 18 40990389067797283140009984000000 19 14797530453474819213543604224000000 20 5919012181389927685417441689600000000

Recurrences

!n  =  !(n − 1) ⋅  n + (−1) n, n ≥ 1.

!n  =  (n − 1) ⋅  [!(n − 1) + !(n − 2)], n ≥ 2.

Note that the factorial has a similar recurrence

n!  =  (n − 1) ⋅  [(n − 1)! + (n − 2)!], n ≥ 2.

So, for

n   ≥   2,

!n !(n − 1) + !(n − 2)  =  n − 1  =  n! (n − 1)! + (n − 2)! .

Other formulae

!n  =  Γ (n + 1, −1) e ,

where

e

(Cf. A001113) is Euler’s number and

Γ (z, a)

is the incomplete gamma function.

A very good approximation is given by

!n  ≈  n! e .

If rounded, you get a perfect formula for

n   ≥   1

!n  =  n! e  =  n! e + 1 2 , n ≥ 1.

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

n   ≥   1

!n  =  n! + 1 e , n ≥ 1,

Comparison with approximations

n	!n	n! e	n! e	n! + 1 e	n! + 1 e
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

[n]

is the round function and

⌊  n⌋

is the floor function. There is a sequence (Cf. A000255)

an = !(n + 1) + !n = !(n + 2) n + 1

with the members

a 0 = 1, a1 = 1,

and the recursive rule:

an  =  n ⋅  an  − 1 + (n − 1) ⋅  an  − 2 .

With this sequence you can calculate the subfactorial

!n  =  (n − 1) ⋅  an  − 2 .

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

Generating function

Ordinary generating function

G{!n}(x)  ≡   ∞ ∑   n  = 0     !n x n  =  1 x  ⋅   Ei (1 + 1 / x) e (1 + 1 / x) ,

where

Ei (x)

is the exponential integral.

Exponential generating function

E{!n}(x)  ≡   ∞ ∑   n  = 0     !n x n n!  =  e  − x 1 − x .

Asymptotic behaviour

The limit of the quotient of

n

factorial and

n

subfactorial converges to

e

(Cf. A001113 and Euler’s number)

n → ∞limn → ∞  n! !n  =  e .

Proof:

e  x  =    ∞ ∑   k  = 0    x k k ! , e  =  e 1  =    ∞ ∑   k  = 0    1 k ! ,  1 e  =  e  − 1  =    ∞ ∑   k  = 0    (−1) k k ! ,

n → ∞limn → ∞  n! !n  =  n → ∞limn → ∞  n! n! ∑ n k  = 0 (−1) k k !  =  1 lim n → ∞  ∑ n k  = 0 (−1) k k !  .

The limit of the quotient of the number of arrangements

an

of any subset of

n

distinct objects over the number of derangements

dn

of

n

distinct objects converges to

e 2

(Cf. A072334)

n → ∞limn → ∞  an dn  =  e 2.

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

n → ∞limn → ∞  2√  an  dn  =  n!

Permutations having at least one fixed point

The number of permutations

fn

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

fn  =  n! − !n  =  n! − n!   n ∑   k  = 0    (−1) k k !  =  n!   n ∑   k  = 1    (−1) k k ! ,

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

n = 0

.

Sequences

A000166 Subfactorial numbers (or rencontres numbers, or derangements: number of permutations of

n

elements with no fixed points)

!n, n   ≥   0.

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

A000255

a (n) = !(n + 1) + !n = !(n + 2) n + 1 = n a (n  −  1) + (n  −  1) a (n  −  2), a (0) = 1, a (1) = 1.

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

A002467 Number

n!  −  !n

of permutations of

n, n   ≥   0,

having a fixed point.

{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)

• Rencontres numbers (number of partial derangements)
• Generalized derangement numbers

• Factorial

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., as of 2010-12-19.
• Weisstein, Eric W., Subfactorial, from MathWorld—A Wolfram Web Resource., as of 2010-12-19.