AFTD Auto-Formalizing Theoretical Domains

perm_offset_avoiding_count

def

a_S(n): the number of S-avoiding permutations of an n-element set, i.e. permutations pi of {0, ..., n-1} with pi(i) - i - s not divisible by n for every i and every s in S. With S = {-1, 0} this is the menage number U(n).

Statement

def perm_offset_avoiding_count (n : ℕ) (S : Finset ℤ) : ℕ
Defined in
arXiv:2610.23958 (Unranking S-avoiding permutations with two forbidden offsets), Sec. 1 (S-avoiding permutations; U(n) = a_{-1,0}(n)); indices shifted to {0, ..., n-1}, which does not change the condition mod n
Verified
20 Oct 2026
Axioms
none listed
Used by 4

Lean source view module on GitHub

/-- a_S(n): the number of S-avoiding permutations of an n-element set, i.e. permutations pi of {0, ..., n-1} with pi(i) - i - s not divisible by n for every i and every s in S. With S = {-1, 0} this is the menage number U(n). -/
def perm_offset_avoiding_count (n : ℕ) (S : Finset ℤ) : ℕ :=
  (Finset.univ.filter (fun π : Equiv.Perm (Fin n) =>
    ∀ i : Fin n, ∀ s ∈ S, ¬ ((n : ℤ) ∣ ((π i : ℕ) : ℤ) - ((i : ℕ) : ℤ) - s))).card
See it in the graphDiscuss this resultChallenge it