Derangements/Subfactorial Calculator
The number of ways to order n items is given by the factorial function, denoted n!. For example, there are 4! = 24 distinct ways to arrange the four digits 1, 2, 3, and 4:
1234 1243 1324 1342 1423 1432
2134 2143 2314 2341 2413 2431
3124 3142 3214 3241 3412 3421
4123 4132 4213 4231 4312 4321
Of these 24 arrangments, 9 of them are derangements, arrangments where none of the digits appear in their standard position (i.e., 1 in the first position, 2 in the second position, etc.) The 9 derangements are
2143 2341 2413 3142 3412
3421 4123 4312 4321
The number of derangements is also known as the subfactorial function, denoted !n. The subfactorial function can be computed explicitly in terms of the factorial function, or with a number of recursive formulas.
How to Compute !n
Let D(n) = !n and note that D(1) = 0 and D(2) = 1. To find the values of D(n) for n > 2, you can use a second degree recursion formula:D(n) = (n-1)[D(n-1) + D(n-2)].
This expression can be simplified into a first degree recursion formula:
D(n) = nD(n-1) + (-1)n.
The recursive relation above is similar to that of the factorial function, n! = n(n-1)!. Because the two formulas differ only by the addition of ±1, you might expect that the factorial and subfactorial functions grow at a similar rate. Indeed, the ratio n!/!n is more or less constant. As n approaches ∞, the ratio of n! to !n approaches e = 2.7182818....
This gives rise to a more compact expression of !n:
!n = ⌊ (1/e)n! + 1/e ⌋
where ⌊ ⌋ is the floor function. For example, to calculate !4, you evaluate
⌊ (1/e)4! + 1/e ⌋ = ⌊ 8.8291 + 0.3679 ⌋ = ⌊ 9.197 ⌋ = 9
Summation Formula for !n
The number of derangements of n items can also be expressed in terms of the alternating sum of permutations. Let P(n, k) denote the number of permutations of size k out of set of size n. Then D(n) can be computed from the formulaD(n) = Σ P(n, k)(-1)n-k,
where k ranges from 0 to n. For example, the permutations of a set of size 4 are
P(4,0) = 1
P(4,1) = 4
P(4,2) = 12
P(4,3) = 24
P(4,4) = 24
and their alternating sum is
24 - 24 + 12 - 4 + 1 = 9
Integral Formula
The factorial and gamma functions can be expressed as an integral,Γ(n+1) = n! = ∫∞0 e-x xn dx.
The subfactorial can be expressed as a similar integral,
!n = ∫∞0 e-x (x-1)n dx.
© Had2Know 2010