# 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*) =

*n*D(

*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 formula

D(

*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}x

^{n}dx.

The subfactorial can be expressed as a similar integral,

!

*n*= ∫

^{∞}

_{0}e

^{-x}(x-1)

^{n}dx.

© *Had2Know 2010
*