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 \scriptstyle n \, distinct objects (i.e. the number of permutations of \scriptstyle n \, distinct objects with no fixed point) is given by the subfactorial \scriptstyle !n \, of \scriptstyle n \,. The derangement numbers are given by the subfactorial numbers.

Contents

Formula

!n \equiv n! \left(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+ \cdots +(-1)^n\frac{1}{n!}\right) = n! \sum_{k=0}^{n}\frac{(-1)^k}{k!} \,

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 \scriptstyle !n,\, n \,\ge\, 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!\cdot\left(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}-\frac{1}{5!}+\frac{1}{6!}\right) = 265.

Comparison of derangement, permutation and arrangement numbers

Comparison of derangement, permutation and arrangement numbers
n \, Number of derangements

d_n \equiv n! \sum_{k=0}^{n} \frac{(-1)^k}{k!} \,

d_n \approx (1/e) ~ n! \,

d_n = \left[ \frac {n!}{e} \right] = \left\lfloor\frac{n!}{e}+\frac{1}{2}\right\rfloor,\, n \ge 1 \,

Number of permutations

n! \,

Number of arrangements

a_n \equiv n! \sum_{k=0}^{n}\frac{1}{k!} \,

a_n \approx e ~ n! \,

a_n = \left\lfloor e ~ n! \right\rfloor,\, n \ge 1 \,

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

!n =  !(n-1) \cdot n + (-1)^n,\, n \,\ge\, 1. \,
!n = (n-1) \cdot [!(n-1)+!(n-2)],\, n \,\ge\, 2. \,

Note that the factorial has a similar recurrence

n! = (n - 1) \cdot [(n-1)! + (n-2)!],\, n \,\ge\, 2. \,

So, for \scriptstyle n \,\ge\, 2, \,

\frac{!n}{!(n-1)+!(n-2)} = n-1 = \frac{n!}{(n-1)!+(n-2)!}. \,

Other formulae

!n = \frac{\Gamma(n+1, -1)}{e}, \,

where \scriptstyle e \, (Cf. A001113) is Euler's number and \scriptstyle \Gamma(z,a) \, is the incomplete gamma function.

A very good approximation is given by

!n \approx \frac{n!}{e}

If rounded, you get a perfect formula for \scriptstyle n \,\ge\, 1 \,

!n = \left[ \frac {n!}{e} \right] = \left\lfloor\frac{n!}{e}+\frac{1}{2}\right\rfloor,\, n \ge 1.

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

!n = \left\lfloor \frac{n!+1}{e} \right\rfloor,\, n \ge 1, \,
Comparison with approximations
n \, !n \, \frac{n!}{e} \, \left[ \frac {n!}{e} \right] \, \frac{n!+1}{e} \, \left\lfloor \frac{n!+1}{e} \right\rfloor \,
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 \scriptstyle \left[ n \right] \, is the round function and \scriptstyle \left\lfloor n \right\rfloor \, is the floor function.

There is a sequence (Cf. A000255) \scriptstyle a_n \,=\, !(n+1)+!n \,=\, !(n+2)/(n+1) \, with the members \scriptstyle a_0 \,=\, 1,\, a_1 \,=\, 1 \,, and the recursive rule:

a_n = n \cdot a_{n-1} + (n-1) \cdot a_{n-2} \,

With this sequence you can calculate the subfactorial

!n = (n-1) \cdot a_{n-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
a_n \, 1 1 3 11 53 309 2119 16687 148329 1468457 16019531

Generating function

Ordinary generating function

G_{\{!n\}}(x) \equiv \sum_{n=0}^\infty !n ~ x^n = \frac{1}{x} \cdot \frac{{\rm Ei}(1+1/x)}{e^{(1+1/x)}} \,

where \scriptstyle {\rm Ei}(x) \, is the exponential integral.

Exponential generating function

E_{\{!n\}}(x) \equiv \sum_{n=0}^\infty !n ~ \frac{x^n}{n!} = \frac{e^{-x}}{1-x} \,

Asymptotic behaviour

The limit of the quotient of \scriptstyle n\, factorial and \scriptstyle n\, subfactorial converges to \scriptstyle e \, (Cf. A001113 and Euler's number)

\lim_{n \to \infty} \frac{n!}{!n} = e \,

Proof:

e^x = \sum_{k=0}^{\infty} \frac{x^k}{k!},\, e = e^1 = \sum_{k=0}^{\infty} \frac{1}{k!},\, \frac{1}{e} = e^{-1} = \sum_{k=0}^{\infty} \frac{(-1)^k}{k!}, \,
\lim_{n \to \infty} \frac{n!}{!n} = \lim_{n \to \infty} \frac{n!}{n! \sum_{k=0}^{n}\frac{(-1)^k}{k!}} = \frac{1}{\lim_{n \to \infty} \sum_{k=0}^{n}\frac{(-1)^k}{k!}} = \frac{1}{\sum_{k=0}^{\infty} \frac{(-1)^k}{k!}} = \frac{1}{1/e} = e. \,

The limit of the quotient of the number of arrangements \scriptstyle a_n \, of any subset of \scriptstyle n \, distinct objects over the number of derangements \scriptstyle d_n \, of \scriptstyle n \, distinct objects converges to \scriptstyle e^2 \, (Cf. A072334)

\lim_{n \to \infty} \frac{a_n}{d_n} = e^2 \,

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

\lim_{n \to \infty} \sqrt{a_n ~ d_n} = n! \,

Permutations having at least one fixed point

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

f_n = n! - !n = n! - n! \sum_{k=0}^{n}\frac{(-1)^k}{k!} = n! \sum_{k=1}^{n}\frac{(-1)^k}{k!} \,

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

Sequences

The subfactorial numbers (or rencontres numbers, or derangements: number of permutations of \scriptstyle n\, elements with no fixed points) \scriptstyle !n,\, n \ge 0, \, (Cf. A000166) are

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

\scriptstyle a_n \,=\, !(n+1)+!n \,=\, \frac{!(n+2)}{n+1} \,=\, n a(n-1) + (n-1) a(n-2),\, a(0) \,=\, 1,\, a(1) \,=\, 1, \, (Cf. A000255) gives

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

The number \scriptstyle n! - !n \, of permutations of \scriptstyle n,\, n \,\ge\, 0 \,, 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

Personal tools