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
- perm_offset_avoiding_count_eq_sum_pieFor every natural number n and finite subset S ⊆ ℤ, the integer count (perm_offset_avoiding_count n S : ℤ) of S-avoiding permutations…
- perm_offset_avoiding_count_eq_of_board_equivIf bijections sigma (of rows) and rho (of columns) of Fin n carry the forbidden squares of the offset set S exactly onto those of S' -- n…
- perm_offset_avoiding_count_neg_one_one_eq_menage_of_oddFor odd n >= 3 the number of permutations avoiding the offsets {-1, 1} mod n equals the menage number U(n).
- perm_offset_avoiding_count_fourSanity check: U(4) = 2, and there are 4 permutations of 4 elements avoiding the offsets -1 and 1.
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