Subfactorial

The subfactorial, denoted $ !n $, is a mathematical function that counts the number of derangements of a set of $ n $ elements.

Derangements are permutations from which the fixed points (i.e., no element is in its original position) are removed.

The subfactorial of $ n $ is calculated by this formula: $$ !n = n! \sum_{k=0}^n \frac{(-1)^k}{k!} $$

The subfactorial can be defined by recurrence: $$ !n = (n−1) (!(n−1)+!(n−2)) $$ or via another equivalent recurrent relation: $$ !n = n \times !(n-1) + (-1)^n $$

This formula is also used: $$ !n = \left [ \frac {n!}{e} \right ] $$ where brackets [] stands for rounding to the closest integer.

The number of derangements for $ n $ elements is subfactorial of $ n $: $ !n $.

The first values for the first natural numbers are:

— A secretary places 100 letters in 100 envelopes completely randomly. The probability that no letter is in the correct envelope is given by: $ \frac{100!}{!100} \approx \frac{1}{e} \approx 0.36788 \approx 36.7\% $

— A banquet planner assigns $ n $ guests to $ n $ numbered seats, but the guests ignore their assigned seats and each sits randomly. What is the probability that no guest is seated in their correct seat? $ \frac{n!}{!n} \approx \frac{1}{e} \approx 36.7\% $

— $ k $ people place their hats in a box. Then, each person takes a hat at random. What is the probability that no person retrieves their own hat? $ \frac{k!}{!k} \approx \frac{1}{e} \approx 36.7\% $

The subfactorial as the factorial, uses the exclamation mark as symbol but it is written to the left of the number: $ !n $

Sometimes the form $ D_n $ is used in some sources in combinatorics (D for derangements).

By convention, postfixed operators have priority (the calculation goes first) over prefixed, so factorial (postfixed) has priority over subfactorial (prefixed)

The proportion of derangements among all permutations tends to $ \frac{1}{e} $ when $ n $ becomes large, that is: $$ !n \approx n! \times e \\ n! \approx \frac{!n}{e} $$

The subfactorial algorithm is given by the following pseudo-code:
function subfactorial(n) {
memo = [1,0]
for (i = 2 .. n) {
memo[i] = (i - 1) * (memo[i - 1] + memo[i - 2])
}
return memo[n]
}

Time and space complexity: O(n)

If the language already has the factorial function, then it may be faster to use another algorithm.