AFTD Auto-Formalizing Theoretical Domains

perm_cycle_gcd_count

def

The number of permutations $\sigma$ of Fin n whose greatest common divisor of cycle lengths perm_cycle_gcd \sigma equals $g$, where fixed points are counted as cycles of length 1.

Statement

def perm_cycle_gcd_count (n g : ℕ) : ℕ
Defined in
arXiv:2610.40342 Section 6
Verified
31 Oct 2026
Axioms
none listed
Built on 1
  • perm_cycle_gcdThe greatest common divisor of the cycle lengths of a permutation $\sigma$ on a finite type $\alpha$, where fixed points are counted as…

Read back from the Lean

For any two natural numbers n and g, perm_cycle_gcd_count n g is the number of permutations σ of Fin n (i.e., elements of Equiv.Perm (Fin n)) such that perm_cycle_gcd σ = g, where perm_cycle_gcd σ is the greatest common divisor of the lengths of all cycles of σ (including fixed points, which are counted as cycles of length 1).

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

Lean source view module on GitHub

/-- Number of permutations of Fin n whose cycle gcd (including 1-cycles) equals g. -/
def perm_cycle_gcd_count (n g : ℕ) : ℕ := (Finset.univ.filter (fun σ : Equiv.Perm (Fin n) => perm_cycle_gcd σ = g)).card
See it in the graphDiscuss this resultChallenge it