derangements_no_two_cycles_count_three
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
- derangements_no_two_cycles_quotient_threeThe quotient derangements_no_two_cycles_quotient 3 equals 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`.
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.
decide
- The `decide` tactic verifies the identity entirely by computational reflection: Lean evaluates the finite search over all permutations of a 3-element set directly in the kernel.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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