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