AFTD Auto-Formalizing Theoretical Domains

derangements_no_two_cycles_count_three

theoremverified

The number of derangements without 2-cycles of a 3-element set equals 2.

Statement

theorem derangements_no_two_cycles_count_three : derangements_no_two_cycles_count 3 = 2
Source
scout/2610-40342-a-p-adic-valuation-calculus-for-permutations-with-restricte.md:1608
Verified
08 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • derangements_no_two_cycles_countFor a natural number n, derangements_no_two_cycles_count n is the number of permutations of Fin n that have no cycles of length 1 and no…
Used by 1

Read back from the Lean

The number of permutations $\sigma$ of $\mathrm{Fin}\ 3$ such that for every $x \in \mathrm{Fin}\ 3$, the cycle containing $x$ has length neither $1$ nor $2$ (that is, the number of $y \in \mathrm{Fin}\ 3$ such that $\sigma\text{.SameCycle } x\ y$ is not in $\{1, 2\}$) is equal to $2$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The theorem asserts that there are exactly 2 permutations of a 3-element set that have no fixed points and no 2-cycles (namely, the two 3-cycles). Because the symmetric group on 3 elements has order $3! = 6$, this is a finite, decidable search. The proof proceeds entirely by computational reflection via `decide`.

  1. The number of derangements of a 3-element set with no 2-cycles is 2. automation

    The theorem asserts a decidable equality between natural numbers, where the left-hand side counts the permutations of a finite set (`Fin 3`) satisfying a decidable condition. The `decide` tactic performs exhaustive computation across all $3! = 6$ permutations, confirming that only the two 3-cycles have no cycles of length 1 or 2.

    line 3

      decide

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- The number of derangements of Fin 3 with no 2-cycles is 2. -/theorem derangements_no_two_cycles_count_three : derangements_no_two_cycles_count 3 = 2 := by  decide
See it in the graphDiscuss this resultChallenge it