AFTD Auto-Formalizing Theoretical Domains

derangements_no_two_cycles_quotient_three

theoremverified

The quotient derangements_no_two_cycles_quotient 3 equals 1.

Statement

theorem derangements_no_two_cycles_quotient_three : derangements_no_two_cycles_quotient 3 = 1
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 3

Read back from the Lean

The value of derangements_no_two_cycles_quotient 3 is equal to 1, where derangements_no_two_cycles_quotient n is defined as derangements_no_two_cycles_count n / ((n - 1) * (n - 2)) (using natural number division), and derangements_no_two_cycles_count n is the number of permutations σ of Fin n such that for every element x : Fin n, the size of the cycle containing x under σ is not in {1, 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 proof computes the quotient $Q_3 = \text{derangements\_no\_two\_cycles\_quotient}(3)$ directly from its definition. By definition, $Q_3 = \text{derangements\_no\_two\_cycles\_count}(3) / ((3 - 1)(3 - 2))$. Substituting the known count of 2 derangements with no 2-cycles on 3 elements yields $2 / 2 = 1$.

  1. $\text{derangements\_no\_two\_cycles\_quotient}(3) = 1$ automation

    Unfold the definition of $\text{derangements\_no\_two\_cycles\_quotient}(3)$ into $\text{derangements\_no\_two\_cycles\_count}(3) / ((3 - 1) \times (3 - 2))$, rewrite the numerator to $2$ using `derangements_no_two_cycles_count_three`, and evaluate the arithmetic expression $2 / (2 \times 1) = 1$.

    line 3

    uses derangements_no_two_cycles_quotient, derangements_no_two_cycles_count_three

      simp [derangements_no_two_cycles_quotient, derangements_no_two_cycles_count_three]
derangements_no_two_cycles_quotient
the quotient sequence defined for $n \in \mathbb{N}$ by $\text{derangements\_no\_two\_cycles\_count}(n) / ((n - 1)(n - 2))$
derangements_no_two_cycles_count_three
the number of derangements of 3 elements with no 2-cycles is 2

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 quotient Q_3 equals 1. -/theorem derangements_no_two_cycles_quotient_three : derangements_no_two_cycles_quotient 3 = 1 := by  simp [derangements_no_two_cycles_quotient, derangements_no_two_cycles_count_three]
See it in the graphDiscuss this resultChallenge it