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