This site is supported by donations to The OEIS Foundation.

Number of derangements

From OeisWiki
(Redirected from Number of permutations with 0 rencontres)
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 rencontre,[1] 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),[2] 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  dnan
Number of arrangements
an = n!
n
k  = 0
  
1
k !


an   ≈   en!




an =
en!
, 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   ∼   dnan


dnan


(n! ) 2  −  dnan
A001044 A??????  (Add to OEIS?.)[3] A??????  (Add to OEIS?.)[4]
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 xn  = 
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
xn
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!
!n
 =  e .

Proof:

e  x  = 
k  = 0
  
xk
k !
, e  =  e 1  = 
k  = 0
  
1
k !
, 
1
e
 =  e  − 1  = 
k  = 0
  
(−1)k
k !
,
n!
!n
 = 
n!
n!
n

k  = 0
(−1)k
k !
 = 
1
limn → 
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)
an
dn
 =  e 2.

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

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



Notes

  1. “Rencontre” being a french word meaning encounter.
  2. Should be called “rencontre-free” [permutation] numbers, which is french for “encounter-free” [permutation] numbers. Number of permutations with 0 rencontre (encounter), i.e. number of permutations with 0 fixed point.
  3. Add sequence to OEIS?
  4. Add sequence to OEIS?

References