Subfactorial — Definition, Formula & Examples

The subfactorial of a non-negative integer

n

, written

!n

, is the number of derangements of

n

elements — that is, the number of ways to rearrange

n

items so that no item ends up in its original position.

For a non-negative integer $n$ , the subfactorial $!n$ equals the number of permutations $\sigma$ of the set $\{1, 2, \ldots, n\}$ such that $\sigma(i) \neq i$ for all $i$ . It can be computed as $!n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}$ , with the convention $!0 = 1$ .

Key Formula

!n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}

Where:

$n$ = The number of elements being rearranged
$n!$ = The factorial of n (total permutations)
$k$ = Index of summation used in the inclusion-exclusion formula

How It Works

To find

!n

, start with the total number of permutations

n!

and apply the inclusion-exclusion principle to subtract arrangements where at least one element stays fixed. The alternating sum

\sum_{k=0}^{n} \frac{(-1)^k}{k!}

handles the over- and under-counting. As

n

grows,

!n

approaches

\frac{n!}{e}

, so roughly

36.8\%

of all permutations are derangements. You can also use the recurrence

!n = (n-1)(!(n-1) + !(n-2))

with base cases

!0 = 1

and

!1 = 0

Worked Example

Problem: Four friends each bring a gift to a party. The gifts are shuffled and handed back randomly. In how many ways can the gifts be distributed so that no one receives their own gift?

Identify n: There are 4 friends, so

n = 4

Apply the formula: Compute

!4 = 4! \left( \frac{1}{0!} - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!} \right)

!4 = 24 \left(1 - 1 + \frac{1}{2} - \frac{1}{6} + \frac{1}{24}\right)

Simplify: Evaluate the expression inside the parentheses, then multiply by 24.

!4 = 24 \times \frac{3}{8} = 9

Answer: There are 9 ways to distribute the gifts so that nobody gets their own.

Visualization

Why It Matters

Subfactorials appear in probability problems asking for the chance that no object returns to its original position, such as the classic "hat-check" problem. They also show up in combinatorics courses and competition math, and the underlying inclusion-exclusion technique is widely used in discrete mathematics and computer science.

Common Mistakes

Mistake: Confusing

!n

with

n!

and assuming all permutations are derangements.

Correction: The factorial

n!

counts all permutations, while the subfactorial

!n

counts only those where every element moves. For

n = 4

n! = 24

but

!4 = 9