restricted_cycle_perms_count
def
For a natural number n and a finite set S of natural numbers, the number of permutations σ of Fin n such that for every element x of Fin n, the size of the cycle containing x under σ is not in S.
Statement
def restricted_cycle_perms_count (n : ℕ) (S : Finset ℕ) : ℕ- Defined in
- arXiv:2610.40342 Section 1.1
- Verified
- 31 Oct 2026
- Axioms
- none listed
- Used by 11
- restricted_cycle_perms_count_antitoneAdding excluded cycle lengths can only decrease the number of qualifying permutations.
- restricted_cycle_global_gcd_dvd_one_param_gcdFor all r and n, the global gcd restricted_cycle_global_gcd r n divides the one-parameter gcd restricted_cycle_one_param_gcd r n.
- restricted_cycle_global_gcdThe global gcd g_r(n) is the greatest common divisor of the counts restricted_cycle_perms_count n S over all sets S in…
- restricted_cycle_count_as_support_sumIf A is contained in the interval of lengths from r+1 through n, the number of permutations avoiding lengths 1 through r and avoiding the…
- restricted_cycle_global_eq_of_shortFor every r and every positive n less than 2(r+1), the global restricted-cycle gcd equals its one-parameter gcd.
- restricted_cycle_global_eq_iff_family_dvdFor every r and n, equality of the global and one-parameter gcds is equivalent to divisibility of every excluded-family count by the…
- restricted_cycle_global_gcd_eq_support_gcdFor every r and n, the global gcd of counts avoiding cycle lengths 1 through r and any additional subset of lengths up to n equals the gcd…
- derangements_no_two_cycles_countFor a natural number n, derangements_no_two_cycles_count n is the number of permutations of Fin n that have no cycles of length 1 and no…
- restricted_cycle_count_zero_or_base_of_shortFor positive n less than 2(r+1) and an excluded set S containing lengths 1 through r, the restricted count is zero when S contains n and…
- restricted_cycle_one_param_gcdThe one-parameter gcd G_r(n) is the greatest common divisor of the counts restricted_cycle_perms_count n S over all sets S in…
- restricted_cycle_global_gcd_eq_one_param_of_family_dvdIf the one-parameter gcd G_3(n) divides the restricted count a_S(n) attached to every set S = {1,2,3} ∪ T of the excluded family, then the…
Read back from the Lean
The function restricted_cycle_perms_count n S returns the number (as a natural number) of permutations σ of Fin n such that for every x : Fin n, the cardinality of the cycle containing x under σ (the number of y : Fin n such that σ.SameCycle x y) is not in S.
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
/-- The number of permutations of Fin n having no cycle lengths in the finite set S. -/ def restricted_cycle_perms_count (n : ℕ) (S : Finset ℕ) : ℕ := ((Finset.univ : Finset (Equiv.Perm (Fin n))).filter (fun σ => ∀ x : Fin n, (Finset.univ.filter (fun y => σ.SameCycle x y)).card ∉ (S : Set ℕ))).card