Subfactorial

In mathematics, the subfactorial function is a function from the set of natural numbers to itself, whose value at "n" gives the number of permutations of a sequence of "n" distinct values in which none of the elements occur in their original place; such permutations are also known as derangements. In the group-theoretic sense of "permutation", it counts permutations with no fixed point of an "n"-element set. This number of permutations is often written as !"n". By contrast the factorial function of "n", written as "n"!, gives the total number of permutations of a sequence of "n" distinct values.

In practical terms, subfactorial is the number of ways in which "n" persons can each give one present to one other person so that everyone receives a present.

Ths subfactorial function defines sequence in OEIS.

Computing values of the subfactorial function

Subfactorials can be calculated using the inclusion-exclusion principle.

:$!n\; =\; n!\; sum\_\{k=0\}^n\; frac\; \{(-1)^k\}\{k!\}$

Subfactorials can also be calculated in the following ways:

:$!n\; =\; frac\{Gamma\; (n+1,\; -1)\}\{e\}$

where $Gamma$ denotes the incomplete gamma function, and e is the mathematical constant; or

:$!n\; =\; left\; [\; frac\; \{n!\}\{e\}\; ight\; ]\; qquadmbox\{for\; \}ngeq1$

where [x] denotes the nearest integer function.

:$!n\; =\; !(n-1);n\; +\; (-1)^nqquadmbox\{for\; \}ngeq1$:$!n\; =\; (n-1);(!(n-1)+!(n-2))qquadmbox\{for\; \}ngeq2$:$!n\; =\; (n-1);\; a\_\{n-2\}qquadmbox\{for\; \}ngeq2,$where the sequence ("a"_"n")_"n" is given by $;a\_0\; =\; a\_1\; =\; 1$ and $a\_n\; =\; n;a\_\{n-1\}\; +\; (n-1);a\_\{n-2\}$; this is sequence

Explicit values

The first few values of the function are:

:!0 = 1:!1 = 0:!2 = 1:!3 = 2:!4 = 9:!5 = 44:!6 = 265:!7 = 1,854:!8 = 14,833:!9 = 133,496:!10 = 1,334,961:!11 = 14,684,570:!12 = 176,214,841:!13 = 2,290,792,932:!14 = 32,071,101,049:!15 = 481,066,515,734:!16 = 7,697,064,251,745:!17 = 130,850,092,279,664:!18 = 2,355,301,661,033,953:!19 = 44,750,731,559,645,106:!20 = 895,014,631,192,902,121:!21 = 18,795,307,255,050,944,540

Miscellanea

The notation !"n" is not universally accepted. It gives ambiguity with the notation for the factorial function if there is a factor that precedes the subfactorial, which sometimes necessitates an unusual ordering of factors (see for instance in the formulas above), or brackets round the subfactorial.

The number 148,349 is the only number that is equal to the sum of the subfactorials of its digits:

:$148,349\; =\; !1\; +\; !4\; +\; !8\; +\; !3\; +\; !4\; +\; !9$

Subfactorial is sometimes permitted in the Four fours mathematical game where !4 being 9 is helpful.

References

* David Wells, "The Penguin Dictionary of Curious and Interesting Numbers" (2nd ed 1997) ISBN 0 14 026149 4, p.104