The th subfactorial (also called the derangement number; Goulden and Jackson 1983, p. 48; Graham et al. 2003, p. 1050) is the number of permutations of objects in which no object appears in its natural place (i.e., "derangements").
The term "subfactorial "was introduced by Whitworth (1867 or 1878; Cajori 1993, p. 77). Euler (1809) calculated the first ten terms.
The first few values of for , 2, ... are 0, 1, 2, 9, 44, 265, 1854, 14833, ... (OEIS A000166). For example, the only derangements of are and , so . Similarly, the derangements of are , , , , , , , , and , so .
Sums and formulas for include
(1)
| |||
(2)
| |||
(3)
| |||
(4)
|
where is a factorial, is a binomial coefficient, and is the incomplete gamma function.
Subfactorials are implemented in the Wolfram Language as Subfactorial[n].
A plot the real and imaginary parts of the subfactorial generalized to any real argument is illustrated above, with the usual integer-valued subfactorial corresponding to nonnegative integer .
The subfactorials are also called the rencontres numbers and satisfy the recurrence relations
(5)
| |||
(6)
|
The subfactorial can be considered a special case of a restricted rooks problem.
The subfactorial has generating function
(7)
| |||
(8)
| |||
(9)
|
where is the exponential integral, and exponential generating function
(10)
| |||
(11)
| |||
(12)
|
Subfactorials are commonly denoted , (Graham et al. 2003, p. 194), (Dörrie 1965, p. 19), (Pemmaraju and Skiena 2003, p. 106), (Goulden and Jackson 1983, p. 48; van Lint and Wilson 1992, p. 90), or (Riordan 1980, p. 59; Stanley 1997, p. 489), the latter being especially used when viewing them as derangements.
Another equation is given by
(13)
|
where is the usual factorial and is the nearest integer function. M. Hassani (pers. comm., Oct. 28, 2004) gave the forms
(14)
|
for and
(15)
|
for , where is the floor function.
An integral for is given by
(16)
|
A continued fraction for is given by
(17)
|
The numbers of decimal digits in for , 1, ... are 7, 158, 2568, 35660, 456574, 5565709, 65657059, ... (OEIS A114485).
The only prime subfactorial is .
The only number equal to the sum of subfactorials of its digits is
(18)
|
(Madachy 1979).
The subfactorial may be analytically continued to the complex plane, as illustrated above.