Derangement¶

A permutation with no fixed points, so every element moves away from its original position.

Version: v2 · 2026-09-19 · History
Domain-specific #: 4114
Domain group: Formal Sciences
Origin domain: Mathematics
Subdomain: Enumerative Combinatorics → Mathematics
Aliases: Subfactorial permutation

Core Idea¶

The carrier is a permutation of a finite labeled set, not any disordering, partial derangements require separate definitions and subfactorial notation and nearest-integer formulas depend on integer n. Inclusion–exclusion subtracts permutations fixing at least one selected element from all n-factorial permutations, yielding n factorial times the truncated alternating exponential series. The abstraction is therefore identified by a declared carrier, a transformation or constraint over that carrier, and an invariant that tells an analyst whether the named structure is genuinely present.

How would you explain it like I'm…

Nobody Gets Their Own Hat

Everyone at a party puts a hat in a pile, then each person grabs a hat back. If nobody ends up with their own hat, that mix-up is called a derangement. Everyone has a hat, but not one person has the right one.

The Everyone-Moves Shuffle

A permutation is a way of rearranging a set of numbered things, like shuffling cards labeled 1 to n. A derangement is a rearrangement where no item stays in its original spot: card 1 is not in place 1, card 2 is not in place 2, and so on. For 3 cards there are 6 arrangements, and exactly 2 of them are derangements. The number of derangements of n items is written !n and called the subfactorial. For large n, a random shuffle is a derangement a little over a third of the time.

Fixed-Point-Free Permutation

A derangement is a permutation of a finite set with no fixed points, meaning no element i is sent to itself. Counting them uses inclusion-exclusion: start with all n! permutations, subtract those fixing at least one chosen element, add back those fixing at least two, and so on. This gives !n = n!(1 - 1/1! + 1/2! - ... + (-1)^n/n!), which is n! times a cut-off version of the series for e^(-1). So !n is the nearest integer to n!/e, and the chance that a random permutation is a derangement approaches 1/e as n grows. Derangement numbers also satisfy the recurrence !n = (n - 1)(!(n-1) + !(n-2)). Counting permutations with exactly k fixed points, rather than zero, gives the more general rencontres numbers.

In enumerative combinatorics, a derangement of an n-element set is a permutation sigma with no fixed points: sigma(i) != i for every i. The carrier is specifically a permutation of a finite labeled set, not any 'disordering'. The number of derangements D_n, also written !n (the subfactorial), follows from inclusion-exclusion over the events A_i = {sigma(i) = i}: D_n = sum_{k=0}^{n} (-1)^k C(n,k)(n-k)! = n! sum_{k=0}^{n} (-1)^k/k!, a truncation of the exponential series for e^(-1). Hence D_n is the nearest integer to n!/e for n >= 1, and D_n/n! tends to 1/e, the limiting probability that a uniformly random permutation is a derangement. The sequence satisfies D_n = (n - 1)(D_{n-1} + D_{n-2}) with D_0 = 1 and D_1 = 0. The rencontres numbers D_{n,k}, counting permutations with exactly k fixed points, generalize derangements (k = 0). Partial derangements and the nearest-integer formula need their own definitions and integer n.

Scope of Application¶

Derangement belongs to enumerative combinatorics and is useful where the analyst can specify the typed enumerative combinatorics carrier, including objects, relations, parameters, conventions, evidence, boundaries, and comparison targets, then evaluate the finite set and size n, permutation, fixed point condition sigma(i)=i, requirement of zero fixed points, derangement number or subfactorial notation, inclusion–exclusion formula, recurrence and nearest n!/e relation, rencontres-number generalization and probability limit are explicit. The scope is broad within that domain but bounded by the need for the finite set and size n, permutation, fixed point condition sigma(i)=i, requirement of zero fixed points, derangement number or subfactorial notation, inclusion–exclusion formula, recurrence and nearest n!/e relation, rencontres-number generalization and probability limit are explicit.

Clarity¶

The abstraction clarifies a crowded vocabulary by making the finite set and size n, permutation, fixed point condition sigma(i)=i, requirement of zero fixed points, derangement number or subfactorial notation, inclusion–exclusion formula, recurrence and nearest n!/e relation, rencontres-number generalization and probability limit are explicit the center of the account. A claim should name the carrier, the governing operation or relation, the applicable assumptions, and the recognition test.

Manages Complexity¶

Without the abstraction, an analyst must reason directly over many local details: the carrier roles, admissibility assumptions, competing conventions, derived invariants, boundary cases, and proof or validation obligations specific to Derangement. Derangement compresses them into the roles in the structural signature. That compression permits comparison across instances without erasing the variables that determine validity. It also exposes which details may be varied safely and which are constitutive.

Abstract Reasoning¶

Identify the carrier. State what the elements, states, objects, or observations are: the typed enumerative combinatorics carrier, including objects, relations, parameters, conventions, evidence, boundaries, and comparison targets. Reject examples whose alleged carrier belongs to a different problem.
Lock the constitutive rule. Express the finite set and size n, permutation, fixed point condition sigma(i)=i, requirement of zero fixed points, derangement number or subfactorial notation, inclusion–exclusion formula, recurrence and nearest n!/e relation, rencontres-number generalization and probability limit are explicit independently of one notation or implementation.

Knowledge Transfer¶

Knowledge transfers strongly among subfields of enumerative combinatorics because they reuse the typed enumerative combinatorics carrier, including objects, relations, parameters, conventions, evidence, boundaries, and comparison targets, Inclusion–exclusion subtracts permutations fixing at least one selected element from all n-factorial permutations, yielding n factorial times the truncated alternating exponential series., and type the carrier, state every parameter and convention in the definition, test that the finite set and size n, permutation, fixed point condition sigma(i)=i, requirement of zero fixed points, derangement number or subfactorial notation, inclusion–exclusion formula, recurrence and nearest n!/e relation, rencontres-number generalization and probability limit are explicit, compare the nearest accepted identity, and report counterexamples, uncertainty, and limiting cases.

Relationships to Other Abstractions¶

Current abstraction Derangement Domain-specific

Parents (1) — outgoing typed relations

Derangement is a kind of Permutation Prime

It remains its own entry because its identity is fixed by the finite set and size n, permutation, fixed point condition sigma(i)=i, requirement of zero fixed points, derangement number or subfactorial notation, inclusion–exclusion formula, recurrence and nearest n!/e relation, rencontres-number generalization and probability limit.

Hierarchy paths (3) — routes to 1 parentless root

Derangement → is a kind of Permutation → is a kind of Bijectivity → is a kind of Function (Mapping)

Show alternative paths (2)

Neighborhood in Abstraction Space¶

Derangement sits in a crowded region of the domain-specific corpus (8^th percentile for distinctiveness): several abstractions share nearly its structure, so a description that fits it tends to fit its neighbors too.

Family — Combinatorial Enumeration & Sequences (38 abstractions)

Nearest neighbors

Lobb number — 0.93
Schröder number — 0.93
Eulerian number — 0.93
Piecewise syndetic set — 0.92
Motzkin number — 0.91

Computed from structural-signature embeddings · 2026-10-25