Subfactorial

The number of Permutations of $n$ objects in which no object appear in its natural place (i.e., so-called ``Derangements'').

$$!n \equiv n!\sum_{k=0}^n {(-1)^k\over k!}$$ (1)

or

$$!n\equiv\left[{n!\over e}\right],$$ (2)

where $k!$ is the usual Factorial and $[x]$ is the Nint function. The first few values are $!1=0$, $!2=1$, $!3=2$, $!4=9$, $!5=44$, $!6=265$, $!7=1854$, $!8=14833$, ... (Sloane's A000166). For example, the only Derangements of $\{1,2,3\}$ are $\{2,3,1\}$ and $\{3,1,2\}$, so $!3=2$. Similarly, the Derangements of $\{1,2,3,4\}$ are $\{2,1,4,3\}$, $\{2,3,4,1\}$, $\{2,4,1,3\}$, $\{3,1,4,2\}$, $\{3,4,1,2\}$, $\{3,4,2,1\}$, $\{4,1,2,3\}$, $\{4,3,1,2\}$, and $\{4,3,2,1\}$, so $!4=9$.

The subfactorials are also called the Rencontres Numbers and satisfy the Recurrence Relations

$$!n=n\cdot !(n-1)+(-1)^{n}$$ (3)

$$!(n+1)=n[!n+!(n-1)].$$ (4)

The subfactorial can be considered a special case of a restricted Rooks Problem.

The only number equal to the sum of subfactorials of its digits is

$$148,349=!1+!4+!8+!3+!4+!9$$ (5)

(Madachy 1979).

See also Derangement, Factorial, Married Couples Problem, Rooks Problem, Superfactorial

References

Dörrie, H. §6 in 100 Great Problems of Elementary Mathematics: Their History and Solutions. New York: Dover, pp. 19-21, 1965.

Madachy, J. S. Madachy's Mathematical Recreations. New York: Dover, p. 167, 1979.

Sloane, N. J. A. Sequence A000166/M1937 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html and extended entry in Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.

Stanley, R. P. Enumerative Combinatorics, Vol. 1. Cambridge, England: Cambridge University Press, p. 67, 1997.