AFTD Auto-Formalizing Theoretical Domains

perm_offset_rook_number

def

Given a natural number n, a finite subset S ⊆ ℤ, and k ∈ ℕ, perm_offset_rook_number n S k is the number of k-element subsets R of cells (i, j) ∈ Fin n × Fin n satisfying ∃ s ∈ S, (n : ℤ) ∣ ((j : ℕ) : ℤ) - ((i : ℕ) : ℤ) - s, such that no two distinct elements of R share a row or a column (∀ c1 c2 ∈ R, c1 ≠ c2 → c1.1 ≠ c2.1 ∧ c1.2 ≠ c2.2).

Statement

def perm_offset_rook_number (n : ℕ) (S : Finset ℤ) (k : ℕ) : ℕ
Defined in
arXiv:2610.23958 Definition 2.2 and Equation (2)
Verified
24 Oct 2026
Axioms
none listed
Used by 2

Read back from the Lean

perm_offset_rook_number n S k is defined as the number of subsets $R$ of size $k$ of the board of cells $$\{ (r, c) \in \mathrm{Fin}(n) \times \mathrm{Fin}(n) \mid \exists s \in S,\ (n : \mathbb{Z}) \mid ((c : \mathbb{Z}) - (r : \mathbb{Z}) - s) \}$$ such that no two distinct cells in $R$ share a row or a column (that is, for all $c_1, c_2 \in R$, if $c_1 \neq c_2$, then $c_1.1 \neq c_2.1$ and $c_1.2 \neq c_2.2$).

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 k-th rook number r_k(n, S): number of k-element nonattacking placements on the forbidden board of cells (i, j) with n dividing j - i - s for some s in S. -/
def perm_offset_rook_number (n : ℕ) (S : Finset ℤ) (k : ℕ) : ℕ :=
  open Classical in
  (((Finset.univ : Finset (Fin n × Fin n)).filter (fun c =>
    ∃ s ∈ S, (n : ℤ) ∣ ((c.2 : ℕ) : ℤ) - ((c.1 : ℕ) : ℤ) - s)).powersetCard k).filter (fun R =>
    ∀ c1 ∈ R, ∀ c2 ∈ R, c1 ≠ c2 → c1.1 ≠ c2.1 ∧ c1.2 ≠ c2.2) |>.card
See it in the graphDiscuss this resultChallenge it