AFTD Auto-Formalizing Theoretical Domains

perm_cycle_gcd_mult_count

def

The number of permutations of Fin n whose cycle-length gcd (fixed points counted as 1-cycles) is a multiple of m. Equivalently (for m > 0), the number of permutations of {1, ..., n} all of whose cycle lengths are divisible by m; this is the quantity b_d(n) of the source paper.

Statement

def perm_cycle_gcd_mult_count (n m : ℕ) : ℕ
Source
step towards perm_cycle_gcd_dvd_pred
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…

Lean source view module on GitHub

/-- Number of permutations of `Fin n` whose cycle-length gcd is a multiple of `m`. -/
def perm_cycle_gcd_mult_count (n m : ℕ) : ℕ := (Finset.univ.filter (fun σ : Equiv.Perm (Fin n) => m ∣ perm_cycle_gcd σ)).card
See it in the graphDiscuss this resultChallenge it