(Redirected from Number of permutations with 0 rencontres)
There are no approved revisions of this page, so it may
not have been
reviewed.
This article needs more work.
Please help by expanding it!
The number of (complete)
derangements, or
number of permutations with no rencontre,
[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
-
!n := n! 1 − + − + ⋯ + (−1) n = n! . |
Subfactorial numbers
A000166 Subfactorial (
rencontres numbers),
[2] or
derangements: number of permutations of
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
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 − + − + − + = 265. |
Comparison of derangement, permutation and arrangement numbers
Comparison of derangement, permutation and arrangement numbers
|
Number of derangements
|
Number of permutations
|
Number of arrangements
|
|
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
|
|
|
|
|
|
|
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
-
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:
-
an = n ⋅ an − 1 + (n − 1) ⋅ an − 2 . |
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
-
G{!n}(x) ≡ !n x n = ⋅ Ei (1 + 1 / x) | e (1 + 1 / x) | , |
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:
-
e x = , e = e 1 = , = e − 1 = , |
-
n → ∞limn → ∞ = n → ∞limn → ∞ = . |
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
-
n → ∞limn → ∞ 2√ an dn = n! |
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
-
fn = n! − !n = n! − n! = n! , |
where the second summation gives the
empty sum (defined as the
additive identity, i.e.
0) for
.
Sequences
A000166 Subfactorial numbers (or
rencontres numbers, or
derangements: number of permutations of
elements with no fixed points)
-
{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 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
of permutations of
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
- ↑ “Rencontre” being a french word meaning encounter.
- ↑ 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.
- ↑ Add sequence to OEIS?
- ↑ Add sequence to OEIS?
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.