Subfactorial

SubFactorial \( n \) is a calculated using this formula: $$ !n = n! \sum_{k=0}^n \frac {(-1)^k}{k!} $$

Example: $$ \begin{align} !4 &= 4! ( \frac{(-1)^0}{0!} + \frac{(-1)^1}{1!} + \frac{(-1)^2}{2!} + \frac{(-1)^3}{3!} + \frac{(-1)^4}{4!} ) \\ &= 4! \times ( 1/1 - 1/1 + 1/2 - 1/6 + 1/24 ) \\ &= 24 \times 9/24 \\ &= 9 \end{align} $$

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

Example: \( 4! / e \approx 24/2.718 \approx 8.829 \Rightarrow !4 = 9 \)

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

Derangements (or Rencontres) are permutations without the one with fixed points (no item is in its original place). The number of derangements for \( n \) elements is subfactorial of \( n \): \( !n \).

Example: The \( !4 = 9 \) 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}.