TheoremStatement: Literature-sourcedProof: AI-adaptedSession-authored (Fable 5 assisted)precheck passverified 2026-08-03 (gpt-5.6-sol-codex-subscription)

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced — the exact statement appears in a cited source; only wording and notation differ.
AI-adapted — a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated — a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

$\iota(D_n) = \iota(n!)\sum_{i<n+1}(-1)^{i}/\iota(i!)$ , with the term at $i = 0$ equal to $1$ and $D_0 = 1$

Statement

For every $n \in \mathbb{N}$ , in $\mathbb{R}$ ,

$\iota(D_n) \;=\; \iota(n!)\sum_{i<n+1}\frac{(-1)^{i}}{\iota(i!)},$

where $D_n$ is the derangement number (The derangement number $D_n$ : the number of bijections of an $n$ -element set with no fixed point), $n!$ the factorial (The factorial $n!$ and the falling factorial $n^{\underline{k}}$ , defined by recursion in $\mathbb{N}$ ) and $\iota$ the canonical natural (The canonical natural $\iota(n) = n \cdot 1_F$ of a field). Each division is legitimate because $i! \ne 0$ , hence $\iota(i!) \ne 0$ .

The index runs from $0$ , and the term at $i = 0$ is $(-1)^{0}/\iota(0!) = 1$ . At $n = 0$ the identity reads $\iota(D_0) = \iota(0!)\cdot 1 = 1$ , which agrees with $D_0 = 1$ ; at $n = 1$ it reads $\iota(D_1) = 1\cdot(1-1) = 0$ ; and at $n = 2$ it reads $\iota(D_2) = 2\cdot(1-1+1/2) = 1$ .

Since $\iota$ is injective, the identity determines $D_n$ as a natural number (Laws of finite sums and products in $\mathbb{N}$ , and $\iota\big(\sum_{k<n} a_k\big) = \sum_{k<n} \iota(a_k)$ , clause 7).

Facts & Assumptions

Given: A natural number $n$ , the set $X := \operatorname{Bij}(n)$ of bijections of $n$ onto itself, and, for $a \in n$ , the set $A_a := \{\, f \in X : f(a) = a \,\}$ of bijections fixing $a$ .

[L1]

$\operatorname{Bij}(S)$ is finite with $\lvert\operatorname{Bij}(S)\rvert = \lvert S\rvert!$ for every finite $S$ (A finite set $A$ with $\lvert A\rvert = n$ has exactly $n!$ bijections onto itself, and $n!$ bijections onto any set of the same cardinality, The factorial $n!$ and the falling factorial $n^{\underline{k}}$ , defined by recursion in $\mathbb{N}$ ); in particular $\lvert X\rvert = n!$ and $\lvert n\rvert = n$ (The cardinality $\lvert A\rvert$ of a finite set).

[L2]

$(A_a)_{a \in n}$ is a family of subsets of the finite set $X$ indexed by the finite set $n$ , hence a sieve family with ambient set $X$ , and $A_\varnothing = X$ (A finite family $(A_i)_{i \in I}$ of subsets of a finite set $X$ , the intersections $A_J$ for $J \subseteq I$ , and the convention $A_\varnothing = X$ , A subset of a finite set is finite, with $\lvert B\rvert \le \lvert A\rvert$ , and equality holds if and only if $B = A$ ).

[L3]

$\operatorname{Der}(n) = X \setminus \bigcup_{a \in n}A_a$ , since a bijection of $n$ is a derangement exactly when it fixes no point (The derangement number $D_n$ : the number of bijections of an $n$ -element set with no fixed point, Injection, surjection, bijection).

[L4]

For a finite sieve family $(A_a)_{a\in n}$ in $X$ with $A_\varnothing=X$ , the complementary identity is $\iota|X\setminus\bigcup_{a\in n}A_a|=\sum_{J\in\mathcal P(n)}(-1)^{|J|}\iota|A_J|$ (Inclusion and exclusion: $\iota\lvert\bigcup_{i \in I} A_i\rvert = \sum_{\varnothing \ne J \subseteq I}(-1)^{\lvert J\rvert + 1}\,\iota\lvert A_J\rvert$ , together with the complementary form counting the elements in none of the $A_i$ , clause 2).

[L5]

Partition of a power set by cardinality: the sets $[n]^{i}$ for $i \in \sigma(n)$ are pairwise disjoint with union $\mathcal{P}(n)$ , and $\lvert [n]^{i}\rvert = \binom{n}{i}$ (A subset of a finite set is finite, with $\lvert B\rvert \le \lvert A\rvert$ , and equality holds if and only if $B = A$ , clause 2, The set $[A]^{k}$ of $k$ -element subsets and the binomial coefficient $\binom{n}{k} := \lvert [n]^{k}\rvert$ , $\lvert\mathcal{P}(A)\rvert = 2^{\lvert A\rvert}$ for finite $A$ ).

[L6]

Splitting a sum along a partition of its index set (The sum rule: a finite disjoint union is finite with $\lvert A \cup B\rvert = \lvert A\rvert + \lvert B\rvert$ and $\lvert\bigcup_{i \in I} A_i\rvert = \sum_{i \in I}\lvert A_i\rvert$ , and a sum over a finite index set splits along a partition, clause 3); a constant real summand and the bridge $\sum_{i \in n}u_i = \sum_{i<n}u_i$ (The sum $\sum_{i \in S} a_i$ over a finite index set, and its product form, clauses (a) and (c)); and scaling of a real finite sum (Laws of finite sums and finite products, clause 2, Finite sums and finite products, by recursion).

[L7]

For $J \subseteq n$ : $\lvert J\rvert + \lvert n\setminus J\rvert = n$ , so $\lvert n\setminus J\rvert = n - \lvert J\rvert$ with the truncated difference (The sum rule: a finite disjoint union is finite with $\lvert A \cup B\rvert = \lvert A\rvert + \lvert B\rvert$ and $\lvert\bigcup_{i \in I} A_i\rvert = \sum_{i \in I}\lvert A_i\rvert$ , and a sum over a finite index set splits along a partition, clause 1, Finite sums and finite products of natural numbers, $\sum_{k<n} a_k$ and $\prod_{k<n} a_k$ in $\mathbb{N}$ ).

[L8]

Integrality of the binomial coefficient: for $i \le n$ , $\iota\binom{n}{i} = \iota(n!)/\big(\iota(i!)\,\iota((n-i)!)\big)$ ( $\binom{n}{k}\,k!\,(n-k)! = n!$ for $k \le n$ ; hence $\binom{n}{k}\,k! = n^{\underline{k}}$ , the quotient $n!/(k!(n-k)!)$ is a natural number, and $\binom{n}{k} = \binom{n}{n-k}$ , clause 2); and $m! \ne 0$ for every $m$ , so $\iota(m!) \ne 0$ (The factorial $n!$ and the falling factorial $n^{\underline{k}}$ , defined by recursion in $\mathbb{N}$ , clause (b), Laws of finite sums and products in $\mathbb{N}$ , and $\iota\big(\sum_{k<n} a_k\big) = \sum_{k<n} \iota(a_k)$ , clause 7).

[L9]

$\mathbb{R}$ is an ordered field, so division by a nonzero element is available (Ordered field, Field); and $(-1)^{0} = 1$ (Integer powers $a^m$ ).

Proof

technique · direct

1.1

The ambient set and the sieve family. $X = \operatorname{Bij}(n)$ is finite with $\lvert X\rvert = n!$ by [L1], the sets $A_a$ for $a \in n$ are subsets of $X$ , and $\operatorname{Der}(n)$ is the complement in $X$ of their union by [L3].

L1L2L3construct

1.2

The intersections are bijection sets of a smaller set. For $J \subseteq n$ the map $f \mapsto f\!\restriction\!(n\setminus J)$ is a bijection of $A_J$ onto $\operatorname{Bij}(n\setminus J)$ . Indeed a bijection $f$ of $n$ fixing every point of $J$ has $f[J] = J$ , hence $f[n\setminus J] = n \setminus J$ by injectivity, so its restriction is a bijection of $n\setminus J$ ; conversely a bijection $g$ of $n\setminus J$ extends by the identity on $J$ to a bijection of $n$ fixing every point of $J$ , and the two constructions are mutually inverse. For $J = \varnothing$ both sides are $X$ , by the stipulation of [L2].

L1L2L3construct

1.3

Hence $\lvert A_J\rvert = \lvert n\setminus J\rvert! = (n - \lvert J\rvert)!$ for every $J \subseteq n$ , by [L1] applied to $n\setminus J$ and by [L7].

L1L7

2.1

The sieve. Applying [L4] to the family of step 1.1 and substituting step 1.3, $\iota(D_n) = \iota\lvert\operatorname{Der}(n)\rvert = \sum_{J \in \mathcal{P}(n)}(-1)^{\lvert J\rvert}\,\iota\big((n-\lvert J\rvert)!\big)$ .

step 1.1step 1.2step 1.3L4

3.1

Grouping the subsets of $n$ by size. Splitting along the partition of [L5] and using the constant clause of [L6] on each block, where the summand depends on $J$ only through $\lvert J\rvert = i$ , gives $\iota(D_n) = \sum_{i<n+1}\iota\binom{n}{i}\,(-1)^{i}\,\iota\big((n-i)!\big)$ .

step 2.1L5L6

4.1

Each coefficient collapses. For $i < n+1$ , that is $i \le n$ , [L8] gives $\iota\binom{n}{i}\,\iota\big((n-i)!\big) = \iota(n!)/\iota(i!)$ , so the $i$ -th summand of step 3.1 is $(-1)^{i}\,\iota(n!)/\iota(i!)$ ; scaling the sum by the constant $\iota(n!)$ through [L6] gives $\iota(D_n) = \iota(n!)\sum_{i<n+1}(-1)^{i}/\iota(i!)$ .

step 3.1L6L8L9∎

Remarks

Where the closed formula for the binomial coefficient is spent. Only in the last step, and only in the range $i \le n$ , which is exactly the range the sum runs over. Outside that range the identity of $\binom{n}{k}\,k!\,(n-k)! = n!$ for $k \le n$ ; hence $\binom{n}{k}\,k! = n^{\underline{k}}$ , the quotient $n!/(k!(n-k)!)$ is a natural number, and $\binom{n}{k} = \binom{n}{n-k}$ is not asserted, and it is not used.
Why the identity is stated in $\mathbb{R}$ . It contains both a subtraction, through the alternating sign, and a division by $i!$ . Neither operation exists in $\mathbb{N}$ , so the count is carried across by $\iota$ ; injectivity of $\iota$ is what carries the conclusion back.
The first index is $0$ and it matters. The term at $i = 0$ is $1$ , and the identity at $n = 0$ is the statement $D_0 = 1$ , which is where the empty function enters. A version of this formula whose sum began at $i = 1$ would be false at every $n$ .

Depends on

Used by

Dependency tree · next 3 levels

Direct dependencies and their dependencies through the next three levels: 95 results over 31 levels. An arrow runs from a result to what uses it, and this result sits at the bottom with a heavier outline. Click the chart to enlarge it.

Sources

Derangement (Wikipedia) (standard reference, not scraped)
Inclusion-exclusion principle (Wikipedia) (standard reference, not scraped)
Rencontres numbers (Wikipedia) (standard reference, not scraped)
Derangements (OpenText at the University of Lethbridge) (standard reference, not scraped)

ι(Dn)=ι(n!)∑i<n+1(−1)i/ι(i!)\iota(D_n) = \iota(n!)\sum_{i<n+1}(-1)^{i}/\iota(i!)ι(Dn​)=ι(n!)∑i<n+1​(−1)i/ι(i!), with the term at i=0i = 0i=0 equal to 111 and D0=1D_0 = 1D0​=1