TOPICS
Search

Subfactorial


The nth subfactorial (also called the derangement number; Goulden and Jackson 1983, p. 48; Graham et al. 2003, p. 1050) is the number of permutations of n 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 !n for n=1, 2, ... are 0, 1, 2, 9, 44, 265, 1854, 14833, ... (OEIS 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.

Sums and formulas for !n include

!n=n!sum_(k=0)^(n)((-1)^k)/(k!)
(1)
=sum_(k=0)^(n)k!(-1)^(n-k)(n; k)
(2)
=sum_(k=0)^(n)(n!(-1)^(n-k))/((n-k)!)
(3)
=(Gamma(n+1,-1))/e
(4)

where n! is a factorial, (n; k) is a binomial coefficient, and Gamma(a,z) is the incomplete gamma function.

Subfactorials are implemented in the Wolfram Language as Subfactorial[n].

Subfactorial

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

The subfactorials are also called the rencontres numbers and satisfy the recurrence relations

!n=n·!(n-1)+(-1)^n
(5)
!n=(n-1)[!(n-2)+!(n-1)].
(6)

The subfactorial can be considered a special case of a restricted rooks problem.

The subfactorial has generating function

G(x)=(e^(-(1+1/x)))/xEi(1+1/x)
(7)
=sum_(n=0)^(infty)(!n)x^n
(8)
=1+x^2+2x^3+9x^4+44x^5+265x^6+...,
(9)

where Ei(x) is the exponential integral, and exponential generating function

E(x)=(e^(-x))/(1-x)
(10)
=sum_(n=0)^(infty)(!n)(x^n)/(n!)
(11)
=1+1/2x^2+1/3x^3+3/8x^4+(11)/(30)x^5+...
(12)

(OEIS A053557 and A053556).

Subfactorials are commonly denoted !n, n!` (Graham et al. 2003, p. 194), n^_ (Dörrie 1965, p. 19), d(n) (Pemmaraju and Skiena 2003, p. 106), d_n (Goulden and Jackson 1983, p. 48; van Lint and Wilson 1992, p. 90), or D_n (Riordan 1980, p. 59; Stanley 1997, p. 489), the latter being especially used when viewing them as derangements.

Another equation is given by

 !n=[(n!)/e],
(13)

where k! is the usual factorial and [x] is the nearest integer function. M. Hassani (pers. comm., Oct. 28, 2004) gave the forms

 !n=|_(n!+1)/e_|
(14)

for n>=1 and

 !n=|_(e+e^(-1))n!_|-|_en!_|
(15)

for n!=1, where |_x_| is the floor function.

An integral for !n is given by

 int_(-1)^inftyx^ne^(-(x+1))dx=!n.
(16)

A continued fraction for !n is given by

 !n=(n!)/e+((-1)^n)/(n+2-1/(n+3-2/(n+4-3/(n+5-...)))).
(17)

The numbers of decimal digits in !(10^n) for n=0, 1, ... are 7, 158, 2568, 35660, 456574, 5565709, 65657059, ... (OEIS A114485).

The only prime subfactorial is !3=2.

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

 148349=!1+!4+!8+!3+!4+!9
(18)

(Madachy 1979).

SubfactorialReImSubfactorialContours

The subfactorial may be analytically continued to the complex plane, as illustrated above.


See also

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

Explore with Wolfram|Alpha

References

Cajori, F. A History of Mathematical Notations, Vol. 2. New York: Cosimo Classics, 2007.Dörrie, H. §6 in 100 Great Problems of Elementary Mathematics: Their History and Solutions. New York: Dover, pp. 19-21, 1965.Euler, L. "Solution quaestionis curiosae ex doctrina combinationum." Mémoires Académie Sciences St. Pétersbourg 3, 57-64, 1809. Reprinted in Opera Omnia, Series Prima, Vol. 7. Leipzig, Germany: Teubner, pp. 435-440, 1915.Goulden, I. P. and Jackson, D. M. Combinatorial Enumeration. New York: Wiley, 1983.Graham, R. L.; Grötschel, M.; and Lovász, L. (Eds.). Handbook of Combinatorics, Vol. 2. Cambridge, MA: MIT Press, 2003.Madachy, J. S. Madachy's Mathematical Recreations. New York: Dover, p. 167, 1979.Pemmaraju, S. and Skiena, S. Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Cambridge, England: Cambridge University Press, 2003.Riordan, J. An Introduction to Combinatorial Analysis. New York: Wiley, 1980.Sloane, N. J. A. Sequences A000166/M1937, A053556, A053557, and A114485 in "The On-Line Encyclopedia of Integer Sequences."Sloane, N. J. A. and Plouffe, S. Figure M1937 in 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.van Lint, J. H. and Wilson, R. M. A Course in Combinatorics. New York: Cambridge University Press, 1992.Wells, D. The Penguin Dictionary of Curious and Interesting Numbers. Middlesex, England: Penguin Books, p. 27, 1986.Whitworth, W. A. Choice and Chance, Two Chapters of Arithmetic, with an Appendix Containing the Algebraical Treatment of Permutations and Combinations Newly Set Forth. Cambridge, England: Deighton, Bell, 1867.Whitworth, W. A. Messenger Math. 1878.

Referenced on Wolfram|Alpha

Subfactorial

Cite this as:

Weisstein, Eric W. "Subfactorial." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Subfactorial.html

Subject classifications