info prev up next book cdrom email home


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!}
\end{displaymath} (1)

!n\equiv\left[{n!\over e}\right],
\end{displaymath} (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}
\end{displaymath} (3)

\end{displaymath} (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

\end{displaymath} (5)

(Madachy 1979).

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


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.'' 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.

info prev up next book cdrom email home

© 1996-9 Eric W. Weisstein