AFTD Auto-Formalizing Theoretical Domains

perm_offset_avoiding_count_eq_sum_pie

theoremverifiedformalization

For every natural number n and finite subset S ⊆ ℤ, the integer count (perm_offset_avoiding_count n S : ℤ) of S-avoiding permutations equals the sum over k from 0 to n of (-1 : ℤ) ^ k * ((n - k).factorial : ℤ) * (perm_offset_rook_number n S k : ℤ).

Statement

theorem perm_offset_avoiding_count_eq_sum_pie (n : ℕ) (S : Finset ℤ) :
    (perm_offset_avoiding_count n S : ℤ) =
      ∑ k ∈ Finset.range (n + 1), (-1 : ℤ) ^ k * ((n - k).factorial : ℤ) * (perm_offset_rook_number n S k : ℤ)
Formalizes
arXiv:2610.23958 Equation (2)
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • perm_offset_avoiding_counta_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…
  • perm_offset_rook_numberGiven 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…

Read back from the Lean

For every natural number $n$ and every finite set of integers $S$, the number of permutations $\pi$ of $\mathrm{Fin}(n)$ avoiding the offset condition (that is, such that for all $i \in \mathrm{Fin}(n)$ and all $s \in S$, $\pi(i) - i \not\equiv s \pmod n$) is equal to the alternating sum via the principle of inclusion-exclusion: $$\sum_{k=0}^{n} (-1)^k (n - k)! \, r_k(n, S),$$ where $r_k(n, S)$ is the $k$-th rook number, defined as the number of $k$-element subsets of cells $(i, j) \in \mathrm{Fin}(n) \times \mathrm{Fin}(n)$ with $j - i \equiv s \pmod n$ for some $s \in S$ such that no two distinct cells share a row or a column.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The theorem evaluates the number of S-avoiding permutations of Fin n via the Principle of Inclusion-Exclusion applied to the forbidden board X = {(i, j) | ∃ s ∈ S, j - i ≡ s (mod n)}. Writing the avoiding condition as disjointness between the graph of π and X, the empty-set indicator is expanded as an alternating sum over subsets T ⊆ X and the order of summation is swapped. For each subset T, the number of permutations extending T is (n - |T|)! if T is a non-attacking rook placement (proved in the helper lemma) and 0 if T contains conflicting rooks. Partitioning the remaining sum by the number of rooks k = |T| yields the alternating sum over k from 0 to n of (-1)^k (n - k)! times the rook number r_k(n, S).

  1. The projection A = Prod.fst '' T of the rook placement T onto first coordinates satisfies |A| = |T|.

    Let A and B be the images of T under the first and second coordinate projections, respectively. Since T satisfies the non-attacking condition hT (distinct pairs differ in both coordinates), the projection Prod.fst is injective on T. By Finset.card_image_of_injOn, the cardinality of the image A equals |T|.

    lines 6–12

    uses Finset.card_image_of_injOn

      set A := T.image Prod.fst with hA
      set B := T.image Prod.snd with hB
      have hAcard : A.card = T.card := by
        apply Finset.card_image_of_injOn
        intro c1 h1 c2 h2 h
        by_contra hne
        exact (hT c1 h1 c2 h2 hne).1 h
  2. The helper function f : Fin n → Fin n matches each row coordinate in A with its unique paired column coordinate in T.

    Define f(a) as the chosen b with (a, b) ∈ T when such a b exists, and a otherwise. If (a, b) ∈ T, the non-attacking hypothesis hT guarantees uniqueness of the column coordinate, so f(a) = b. Consequently, for any x ∈ A, the pair (x, f(x)) belongs to T.

    lines 13–23

    uses dif_pos, Finset.mem_image.mp

      let f : Fin n → Fin n := fun a => if h : ∃ b, (a, b) ∈ T then h.choose else a
      have hf : ∀ a b, (a, b) ∈ T → f a = b := by
        intro a b hab
        have h : ∃ b, (a, b) ∈ T := ⟨b, hab⟩
        simp only [f, dif_pos h]
        by_contra hne
        exact (hT _ h.choose_spec _ hab (by simp [hne])).1 rfl
      have hfA : ∀ x ∈ A, (x, f x) ∈ T := by
        intro x hx
        obtain ⟨c, hc, rfl⟩ := Finset.mem_image.mp hx
        rw [hf c.1 c.2 hc]; exact hc
  3. The map x ↦ f(x) gives a bijection e : A ≃ B between the row and column coordinates of T.

    The function sending x ∈ A to f(x) ∈ B is injective because f(x₁) = f(x₂) means (x₁, f(x₁)) and (x₂, f(x₂)) share a column in T, which forces x₁ = x₂ by hT. It is surjective because every y ∈ B is the second coordinate of some pair c ∈ T, whose first coordinate c.1 ∈ A satisfies f(c.1) = c.2 = y. By Equiv.ofBijective, this map is an equivalence.

    lines 24–34

    uses Equiv.ofBijective, Subtype.mk.injEq, Subtype.ext, Finset.mem_image.mp, Finset.mem_image.mpr

      let e : {x // x ∈ A} ≃ {y // y ∈ B} := Equiv.ofBijective
        (fun x => ⟨f x.1, Finset.mem_image.mpr ⟨_, hfA x.1 x.2, rfl⟩⟩) (by
          constructor
          · rintro ⟨x1, h1⟩ ⟨x2, h2⟩ h
            simp only [Subtype.mk.injEq] at h
            apply Subtype.ext
            by_contra hne
            exact (hT _ (hfA x1 h1) _ (hfA x2 h2) (by simp [hne])).2 h
          · rintro ⟨y, hy⟩
            obtain ⟨c, hc, rfl⟩ := Finset.mem_image.mp hy
            exact ⟨⟨c.1, Finset.mem_image.mpr ⟨c, hc, rfl⟩⟩, Subtype.ext (hf _ _ hc)⟩)
  4. The bijection e extends to a full permutation τ of Fin n that extends T (τ(c.1) = c.2 for all c ∈ T).

    The subtype equivalence e : A ≃ B between subsets of equal size in Fin n is extended to a permutation τ using Equiv.extendSubtype. For any c ∈ T, its row c.1 belongs to A, so Equiv.extendSubtype_apply_of_mem evaluates τ(c.1) to e(c.1) = f(c.1) = c.2.

    lines 35–41

    uses Finset.mem_image.mpr, Equiv.extendSubtype_apply_of_mem

      let τ : Equiv.Perm (Fin n) := e.extendSubtype
      have hτ : ∀ c ∈ T, τ c.1 = c.2 := by
        intro c hc
        have hm : c.1 ∈ A := Finset.mem_image.mpr ⟨c, hc, rfl⟩
        simp only [τ]
        rw [Equiv.extendSubtype_apply_of_mem e c.1 hm]
        exact hf _ _ hc
  5. Permutations extending T are in bijection with permutations of Fin n that fix A pointwise.

    If π extends T, then τ⁻¹ * π fixes each a = c.1 ∈ A, because (τ⁻¹ * π)(c.1) = τ⁻¹(c.2) = c.1. Conversely, if σ fixes A pointwise, then τ * σ extends T. This provides an explicit two-sided equivalence (key) between {π | ∀ c ∈ T, π c.1 = c.2} and {σ | ∀ a ∈ A, σ a = a}.

    lines 42–56

    uses Fintype.card_subtype, not_not.mp, Finset.mem_image.mp, Equiv.Perm.mul_apply, Finset.mem_image.mpr

      rw [← Fintype.card_subtype]
      have key : {π : Equiv.Perm (Fin n) // ∀ c ∈ T, π c.1 = c.2} ≃
          {σ : Equiv.Perm (Fin n) // ∀ a, ¬ (a ∉ A) → σ a = a} :=
        { toFun := fun π => ⟨τ⁻¹ * π.1, by
            intro a ha
            have ha' : a ∈ A := not_not.mp ha
            obtain ⟨c, hc, rfl⟩ := Finset.mem_image.mp ha'
            rw [Equiv.Perm.mul_apply, π.2 c hc, ← hτ c hc]
            simp⟩
          invFun := fun σ => ⟨τ * σ.1, by
            intro c hc
            have hm : c.1 ∈ A := Finset.mem_image.mpr ⟨c, hc, rfl⟩
            rw [Equiv.Perm.mul_apply, σ.2 c.1 (by simpa using hm), hτ c hc]⟩
          left_inv := fun π => by ext; simp
          right_inv := fun σ => by ext; simp }
  6. The number of permutations extending T is (n - |T|)!.

    Using the bijection key, the count equals the number of permutations fixing A pointwise. By Equiv.Perm.subtypeEquivSubtypePerm, these correspond bijectively to permutations of the complement Aᶜ. The number of such permutations is |Aᶜ|! = (n - |A|)! = (n - |T|)!.

    lines 57–61

    uses Fintype.card_congr, Equiv.Perm.subtypeEquivSubtypePerm, Fintype.card_perm, Fintype.card_subtype, Finset.card_compl, Fintype.card_fin

      rw [Fintype.card_congr key, ← Fintype.card_congr (Equiv.Perm.subtypeEquivSubtypePerm _),
        Fintype.card_perm, Fintype.card_subtype, ← hAcard]
      congr 1
      rw [show (Finset.univ.filter fun x => x ∉ A) = Aᶜ by ext; simp, Finset.card_compl,
        Fintype.card_fin]
  7. Permutations avoiding offset set S are precisely those whose graph is disjoint from the forbidden set X.

    Define X ⊆ Fin n × Fin n as the set of cells c with c.2 - c.1 ≡ s (mod n) for some s ∈ S. The avoiding condition ∀ i, ∀ s ∈ S, n ∤ (π(i) - i - s) means that no graph point (i, π(i)) lies in X, which is equivalent to the filtered set {c ∈ X | π(c.1) = c.2} being empty.

    lines 67–81

    uses Finset.mem_filter, Finset.mem_univ, true_and, Finset.filter_eq_empty_iff

      classical
      set X : Finset (Fin n × Fin n) := Finset.univ.filter
        (fun c => ∃ s ∈ S, (n : ℤ) ∣ ((c.2 : ℕ) : ℤ) - ((c.1 : ℕ) : ℤ) - s) with hX
      have hA : perm_offset_avoiding_count n S = (Finset.univ.filter
          (fun π : Equiv.Perm (Fin n) => X.filter (fun c => π c.1 = c.2) = ∅)).card := by
        unfold perm_offset_avoiding_count
        congr 1
        ext π
        simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.filter_eq_empty_iff, X]
        constructor
        · rintro h c ⟨s, hs, hd⟩ heq
          apply h c.1 s hs
          rw [heq]; exact hd
        · intro h i s hs hd
          exact @h (i, π i) ⟨s, hs, hd⟩ rfl
  8. By the Principle of Inclusion-Exclusion, the count of avoiding permutations equals ∑_{T ⊆ X} (-1)^{|T|} · #{π | ∀ c ∈ T, π(c.1) = c.2}.

    For each permutation π, the indicator of disjointness [X ∩ Γ_π = ∅] is rewritten as the alternating sum ∑_{T ⊆ X ∩ Γ_π} (-1)^{|T|} using Finset.sum_powerset_neg_one_pow_card. Rewriting this as a sum over T ⊆ X conditioned on T ⊆ Γ_π (i.e. π extending T) and swapping the sums over π and T using Finset.sum_comm gives the desired PIE expansion.

    lines 82–107

    uses Finset.natCast_card_filter, Finset.sum_congr, Finset.sum_powerset_neg_one_pow_card, Finset.sum_filter, Finset.mem_powerset, Finset.mem_filter, Finset.subset_iff, Finset.sum_comm, Finset.mul_sum

      have hB : ((Finset.univ.filter
          (fun π : Equiv.Perm (Fin n) => X.filter (fun c => π c.1 = c.2) = ∅)).card : ℤ) =
          ∑ T ∈ X.powerset, (-1 : ℤ) ^ T.card *
            ((Finset.univ.filter (fun π : Equiv.Perm (Fin n) => ∀ c ∈ T, π c.1 = c.2)).card : ℤ) := by
        calc _ = ∑ π : Equiv.Perm (Fin n), ∑ T ∈ (X.filter (fun c => π c.1 = c.2)).powerset,
              (-1 : ℤ) ^ T.card := by
              rw [Finset.natCast_card_filter]
              refine Finset.sum_congr rfl fun π _ => ?_
              rw [Finset.sum_powerset_neg_one_pow_card]
          _ = ∑ π : Equiv.Perm (Fin n), ∑ T ∈ X.powerset,
              if (∀ c ∈ T, π c.1 = c.2) then (-1 : ℤ) ^ T.card else 0 := by
              refine Finset.sum_congr rfl fun π _ => ?_
              rw [← Finset.sum_filter]
              apply Finset.sum_congr _ (fun _ _ => rfl)
              ext T
              simp only [Finset.mem_powerset, Finset.mem_filter, Finset.subset_iff]
              constructor
              · intro h; exact ⟨fun c hc => (h hc).1, fun c hc => (h hc).2⟩
              · rintro ⟨h1, h2⟩ c hc; exact ⟨h1 hc, h2 c hc⟩
          _ = ∑ T ∈ X.powerset, ∑ π : Equiv.Perm (Fin n),
              if (∀ c ∈ T, π c.1 = c.2) then (-1 : ℤ) ^ T.card else 0 := Finset.sum_comm
          _ = _ := by
              refine Finset.sum_congr rfl fun T _ => ?_
              rw [Finset.natCast_card_filter, Finset.mul_sum]
              refine Finset.sum_congr rfl fun π _ => ?_
              split_ifs <;> simp
  9. For any T ⊆ X, the term (-1)^{|T|} · #{π | ∀ c ∈ T, π(c.1) = c.2} equals (-1)^{|T|} (n - |T|)! if T is non-attacking, and 0 otherwise.

    If T is non-attacking (no two cells share a row or column), the auxiliary lemma perm_offset_avoiding_count_eq_sum_pie_extend_card shows the number of extending permutations is (n - |T|)!. If T contains two distinct cells with the same row or column, no permutation π can extend T because permutations are injective functions, making the set of extending permutations empty and the term 0.

    lines 108–131

    uses perm_offset_avoiding_count_eq_sum_pie_extend_card, Finset.filter_eq_empty_iff, Prod.ext

      have hC : ∀ T ∈ X.powerset, (-1 : ℤ) ^ T.card *
          ((Finset.univ.filter (fun π : Equiv.Perm (Fin n) => ∀ c ∈ T, π c.1 = c.2)).card : ℤ) =
          if (∀ c1 ∈ T, ∀ c2 ∈ T, c1 ≠ c2 → c1.1 ≠ c2.1 ∧ c1.2 ≠ c2.2)
          then (-1 : ℤ) ^ T.card * ((n - T.card).factorial : ℤ) else 0 := by
        intro T _
        split_ifs with hP
        · rw [perm_offset_avoiding_count_eq_sum_pie_extend_card n T hP]
        · have hE : Finset.univ.filter (fun π : Equiv.Perm (Fin n) => ∀ c ∈ T, π c.1 = c.2) = ∅ := by
            rw [Finset.filter_eq_empty_iff]
            intro π _ hπ
            apply hP
            intro c1 h1 c2 h2 hne
            have e1 := hπ c1 h1
            have e2 := hπ c2 h2
            constructor
            · intro h
              apply hne
              refine Prod.ext h ?_
              rw [← e1, ← e2, h]
            · intro h
              apply hne
              have h' : c1.1 = c2.1 := π.injective (by rw [e1, e2, h])
              exact Prod.ext h' h
          rw [hE]; simp
  10. The sum restricts to non-attacking subsets T ⊆ X, and every such T satisfies |T| ≤ n.

    Substituting the previous step eliminates attacking subsets, leaving only non-attacking T ⊆ X. For any non-attacking T, projection onto the first coordinate is injective by Finset.card_image_of_injOn, so |T| = |Prod.fst '' T| ≤ n (since Fin n has n elements). Therefore |T| ∈ {0, ..., n}.

    lines 132–145

    uses Finset.sum_congr, Finset.sum_filter, Finset.mem_filter.mp, Finset.card_image_of_injOn, Finset.card_le_univ, Finset.mem_range

      rw [hA, hB, Finset.sum_congr rfl hC, ← Finset.sum_filter]
      have hmaps : ∀ T ∈ X.powerset.filter
          (fun T => ∀ c1 ∈ T, ∀ c2 ∈ T, c1 ≠ c2 → c1.1 ≠ c2.1 ∧ c1.2 ≠ c2.2),
          T.card ∈ Finset.range (n + 1) := by
        intro T hT
        have hP := (Finset.mem_filter.mp hT).2
        have h1 : (T.image Prod.fst).card = T.card := by
          apply Finset.card_image_of_injOn
          intro c1 h1 c2 h2 h
          by_contra hne
          exact (hP c1 h1 c2 h2 hne).1 h
        have h2 : (T.image Prod.fst).card ≤ n := by
          simpa using Finset.card_le_univ (T.image Prod.fst)
        rw [Finset.mem_range]; omega
  11. Summing fiberwise by cardinality yields the formula ∑_{k=0}^n (-1)^k (n - k)! r_k(n, S).

    Using Finset.sum_fiberwise_of_maps_to, the sum over non-attacking subsets T is grouped by k = |T| ∈ {0, ..., n}. For a fixed k, the summand (-1)^k (n - k)! is constant and pulls out of the inner sum. The remaining inner sum counts the non-attacking subsets of X of size k, which matches the definition of perm_offset_rook_number n S k.

    lines 146–156

    uses Finset.sum_fiberwise_of_maps_to, Finset.sum_congr, Finset.mem_filter.mp, Finset.sum_const, nsmul_eq_mul, mul_comm, Nat.cast_inj, Finset.mem_filter, Finset.mem_powerset, Finset.mem_powersetCard

      rw [← Finset.sum_fiberwise_of_maps_to hmaps]
      refine Finset.sum_congr rfl fun k _ => ?_
      rw [Finset.sum_congr rfl (fun T hT => by rw [(Finset.mem_filter.mp hT).2]),
        Finset.sum_const, nsmul_eq_mul, mul_comm]
      congr 1
      try simp only [Nat.cast_inj]
      unfold perm_offset_rook_number
      congr 1
      ext T
      simp only [Finset.mem_filter, Finset.mem_powerset, Finset.mem_powersetCard, X]
      tauto
Nat.cast_inj
The natural number cast into integers is injective.
Subtype.mk.injEq
Two subtype elements are equal if and only if their underlying values are equal.
Subtype.ext
Two subtype elements are equal if their underlying values are equal.
not_not.mp
Double negation elimination: ¬¬P implies P.
mul_comm
Multiplication is commutative: a * b = b * a.
nsmul_eq_mul
Scalar multiplication by a natural number n • a equals (n : R) * a.
true_and
The proposition True ∧ P is logically equivalent to P.
dif_pos
A dependent if-then-else expression evaluates to the 'then' branch when the condition holds.
Equiv.ofBijective
A bijective map between types gives an equivalence (bijection).
Equiv.extendSubtype_apply_of_mem
Evaluating the extension of a subtype equivalence on an element of the subtype domain gives its value under the equivalence.
Equiv.Perm.mul_apply
Permutation composition applied to an element satisfies (f * g) x = f (g x).
Equiv.Perm.subtypeEquivSubtypePerm
Permutations of a subtype are equivalent to permutations of the ambient space that fix every element outside the subtype.
Fintype.card_perm
The number of permutations of a finite type of cardinality m is m!.
Fintype.card_congr
Equivalent finite types have identical cardinalities.
Fintype.card_subtype
The cardinality of a subtype equals the number of elements of the ambient type satisfying the defining predicate.
Fintype.card_fin
The cardinality of Fin n is n.
Finset.card_image_of_injOn
If a map is injective on a finite set s, its image has the same cardinality as s.
Finset.card_compl
The complement of a subset s in a finite type has cardinality equal to the ambient type's cardinality minus |s|.
Finset.mem_filter
An element is in Finset.filter p s if and only if it is in s and satisfies p.
Finset.mem_filter.mp
Extracts membership in the base set and satisfaction of the condition from membership in a filtered finset.
Finset.mem_univ
Every element of a finite type belongs to the universal finset Finset.univ.
Finset.mem_image.mp
An element is in the image of a set if and only if it is the image of some element in the set (left-to-right direction).
Finset.mem_image.mpr
An element is in the image of a set if and only if it is the image of some element in the set (right-to-left direction).
Finset.filter_eq_empty_iff
A filtered set is empty if and only if no element of the base set satisfies the predicate.
Finset.natCast_card_filter
The cardinality of a filtered subset cast to a ring equals the sum of indicator values (1 if true, 0 if false).
Finset.sum_congr
Two finite sums are equal if their index sets are equal and their summands agree everywhere on the set.
Finset.sum_powerset_neg_one_pow_card
The alternating sum of powers of -1 over all subsets of a set x is 1 if x is empty and 0 otherwise.
Finset.sum_filter
Summing over a filtered set equals summing the conditional expression (if p then f else 0) over the ambient set.
Finset.mem_powerset
A set T belongs to Finset.powerset s if and only if T ⊆ s.
Finset.subset_iff
Subset inclusion s ⊆ t means every element of s belongs to t.
Finset.sum_comm
Double finite sums commute: summing over x then y equals summing over y then x.
Finset.mul_sum
Multiplication distributes over finite summation: a * ∑ i, f i = ∑ i, a * f i.
Prod.ext
Two ordered pairs are equal if and only if their respective first and second components are equal.
Finset.card_le_univ
The cardinality of any subset of a finite type is at most the cardinality of the type.
Finset.mem_range
A natural number m is in Finset.range n if and only if m < n.
Finset.sum_fiberwise_of_maps_to
Partitions a finite sum into fibers of a map g: summing over j in t of the sums over fiber g⁻¹(j) equals the total sum.
Finset.sum_const
Summing a constant value b over a finite set s gives |s| • b.
Finset.mem_powersetCard
A set T is in powersetCard k s if and only if T ⊆ s and |T| = k.
perm_offset_avoiding_count_eq_sum_pie_extend_card
For any non-attacking rook placement T ⊆ Fin n × Fin n, the number of permutations extending T is (n - |T|)!.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

open Classical intheorem perm_offset_avoiding_count_eq_sum_pie_extend_card (n : ℕ) (T : Finset (Fin n × Fin n))    (hT : ∀ c1 ∈ T, ∀ c2 ∈ T, c1 ≠ c2 → c1.1 ≠ c2.1 ∧ c1.2 ≠ c2.2) :    (Finset.univ.filter (fun π : Equiv.Perm (Fin n) => ∀ c ∈ T, π c.1 = c.2)).card      = (n - T.card).factorial := by  set A := T.image Prod.fst with hA  set B := T.image Prod.snd with hB  have hAcard : A.card = T.card := by    apply Finset.card_image_of_injOn    intro c1 h1 c2 h2 h    by_contra hne    exact (hT c1 h1 c2 h2 hne).1 h  let f : Fin n → Fin n := fun a => if h : ∃ b, (a, b) ∈ T then h.choose else a  have hf : ∀ a b, (a, b) ∈ T → f a = b := by    intro a b hab    have h : ∃ b, (a, b) ∈ T := ⟨b, hab⟩    simp only [f, dif_pos h]    by_contra hne    exact (hT _ h.choose_spec _ hab (by simp [hne])).1 rfl  have hfA : ∀ x ∈ A, (x, f x) ∈ T := by    intro x hx    obtain ⟨c, hc, rfl⟩ := Finset.mem_image.mp hx    rw [hf c.1 c.2 hc]; exact hc  let e : {x // x ∈ A} ≃ {y // y ∈ B} := Equiv.ofBijective    (fun x => ⟨f x.1, Finset.mem_image.mpr ⟨_, hfA x.1 x.2, rfl⟩⟩) (by      constructor      · rintro ⟨x1, h1⟩ ⟨x2, h2⟩ h        simp only [Subtype.mk.injEq] at h        apply Subtype.ext        by_contra hne        exact (hT _ (hfA x1 h1) _ (hfA x2 h2) (by simp [hne])).2 h      · rintro ⟨y, hy⟩        obtain ⟨c, hc, rfl⟩ := Finset.mem_image.mp hy        exact ⟨⟨c.1, Finset.mem_image.mpr ⟨c, hc, rfl⟩⟩, Subtype.ext (hf _ _ hc)⟩)  let τ : Equiv.Perm (Fin n) := e.extendSubtype  have hτ : ∀ c ∈ T, τ c.1 = c.2 := by    intro c hc    have hm : c.1 ∈ A := Finset.mem_image.mpr ⟨c, hc, rfl⟩    simp only [τ]    rw [Equiv.extendSubtype_apply_of_mem e c.1 hm]    exact hf _ _ hc  rw [← Fintype.card_subtype]  have key : {π : Equiv.Perm (Fin n) // ∀ c ∈ T, π c.1 = c.2} ≃      {σ : Equiv.Perm (Fin n) // ∀ a, ¬ (a ∉ A) → σ a = a} :=    { toFun := fun π => ⟨τ⁻¹ * π.1, by        intro a ha        have ha' : a ∈ A := not_not.mp ha        obtain ⟨c, hc, rfl⟩ := Finset.mem_image.mp ha'        rw [Equiv.Perm.mul_apply, π.2 c hc, ← hτ c hc]        simp⟩      invFun := fun σ => ⟨τ * σ.1, by        intro c hc        have hm : c.1 ∈ A := Finset.mem_image.mpr ⟨c, hc, rfl⟩        rw [Equiv.Perm.mul_apply, σ.2 c.1 (by simpa using hm), hτ c hc]⟩      left_inv := fun π => by ext; simp      right_inv := fun σ => by ext; simp }  rw [Fintype.card_congr key, ← Fintype.card_congr (Equiv.Perm.subtypeEquivSubtypePerm _),    Fintype.card_perm, Fintype.card_subtype, ← hAcard]  congr 1  rw [show (Finset.univ.filter fun x => x ∉ A) = Aᶜ by ext; simp, Finset.card_compl,    Fintype.card_fin]/-- Principle of inclusion-exclusion expansion of the avoiding count in terms of the rook numbers. -/theorem perm_offset_avoiding_count_eq_sum_pie (n : ℕ) (S : Finset ℤ) :    (perm_offset_avoiding_count n S : ℤ) =      ∑ k ∈ Finset.range (n + 1), (-1 : ℤ) ^ k * ((n - k).factorial : ℤ) * (perm_offset_rook_number n S k : ℤ) := by  classical  set X : Finset (Fin n × Fin n) := Finset.univ.filter    (fun c => ∃ s ∈ S, (n : ℤ) ∣ ((c.2 : ℕ) : ℤ) - ((c.1 : ℕ) : ℤ) - s) with hX  have hA : perm_offset_avoiding_count n S = (Finset.univ.filter      (fun π : Equiv.Perm (Fin n) => X.filter (fun c => π c.1 = c.2) = ∅)).card := by    unfold perm_offset_avoiding_count    congr 1    ext π    simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.filter_eq_empty_iff, X]    constructor    · rintro h c ⟨s, hs, hd⟩ heq      apply h c.1 s hs      rw [heq]; exact hd    · intro h i s hs hd      exact @h (i, π i) ⟨s, hs, hd⟩ rfl  have hB : ((Finset.univ.filter      (fun π : Equiv.Perm (Fin n) => X.filter (fun c => π c.1 = c.2) = ∅)).card : ℤ) =      ∑ T ∈ X.powerset, (-1 : ℤ) ^ T.card *        ((Finset.univ.filter (fun π : Equiv.Perm (Fin n) => ∀ c ∈ T, π c.1 = c.2)).card : ℤ) := by    calc _ = ∑ π : Equiv.Perm (Fin n), ∑ T ∈ (X.filter (fun c => π c.1 = c.2)).powerset,          (-1 : ℤ) ^ T.card := by          rw [Finset.natCast_card_filter]          refine Finset.sum_congr rfl fun π _ => ?_          rw [Finset.sum_powerset_neg_one_pow_card]      _ = ∑ π : Equiv.Perm (Fin n), ∑ T ∈ X.powerset,          if (∀ c ∈ T, π c.1 = c.2) then (-1 : ℤ) ^ T.card else 0 := by          refine Finset.sum_congr rfl fun π _ => ?_          rw [← Finset.sum_filter]          apply Finset.sum_congr _ (fun _ _ => rfl)          ext T          simp only [Finset.mem_powerset, Finset.mem_filter, Finset.subset_iff]          constructor          · intro h; exact ⟨fun c hc => (h hc).1, fun c hc => (h hc).2⟩          · rintro ⟨h1, h2⟩ c hc; exact ⟨h1 hc, h2 c hc⟩      _ = ∑ T ∈ X.powerset, ∑ π : Equiv.Perm (Fin n),          if (∀ c ∈ T, π c.1 = c.2) then (-1 : ℤ) ^ T.card else 0 := Finset.sum_comm      _ = _ := by          refine Finset.sum_congr rfl fun T _ => ?_          rw [Finset.natCast_card_filter, Finset.mul_sum]          refine Finset.sum_congr rfl fun π _ => ?_          split_ifs <;> simp  have hC : ∀ T ∈ X.powerset, (-1 : ℤ) ^ T.card *      ((Finset.univ.filter (fun π : Equiv.Perm (Fin n) => ∀ c ∈ T, π c.1 = c.2)).card : ℤ) =      if (∀ c1 ∈ T, ∀ c2 ∈ T, c1 ≠ c2 → c1.1 ≠ c2.1 ∧ c1.2 ≠ c2.2)      then (-1 : ℤ) ^ T.card * ((n - T.card).factorial : ℤ) else 0 := by    intro T _    split_ifs with hP    · rw [perm_offset_avoiding_count_eq_sum_pie_extend_card n T hP]    · have hE : Finset.univ.filter (fun π : Equiv.Perm (Fin n) => ∀ c ∈ T, π c.1 = c.2) = ∅ := by        rw [Finset.filter_eq_empty_iff]        intro π _ hπ        apply hP        intro c1 h1 c2 h2 hne        have e1 := hπ c1 h1        have e2 := hπ c2 h2        constructor        · intro h          apply hne          refine Prod.ext h ?_          rw [← e1, ← e2, h]        · intro h          apply hne          have h' : c1.1 = c2.1 := π.injective (by rw [e1, e2, h])          exact Prod.ext h' h      rw [hE]; simp  rw [hA, hB, Finset.sum_congr rfl hC, ← Finset.sum_filter]  have hmaps : ∀ T ∈ X.powerset.filter      (fun T => ∀ c1 ∈ T, ∀ c2 ∈ T, c1 ≠ c2 → c1.1 ≠ c2.1 ∧ c1.2 ≠ c2.2),      T.card ∈ Finset.range (n + 1) := by    intro T hT    have hP := (Finset.mem_filter.mp hT).2    have h1 : (T.image Prod.fst).card = T.card := by      apply Finset.card_image_of_injOn      intro c1 h1 c2 h2 h      by_contra hne      exact (hP c1 h1 c2 h2 hne).1 h    have h2 : (T.image Prod.fst).card ≤ n := by      simpa using Finset.card_le_univ (T.image Prod.fst)    rw [Finset.mem_range]; omega  rw [← Finset.sum_fiberwise_of_maps_to hmaps]  refine Finset.sum_congr rfl fun k _ => ?_  rw [Finset.sum_congr rfl (fun T hT => by rw [(Finset.mem_filter.mp hT).2]),    Finset.sum_const, nsmul_eq_mul, mul_comm]  congr 1  try simp only [Nat.cast_inj]  unfold perm_offset_rook_number  congr 1  ext T  simp only [Finset.mem_filter, Finset.mem_powerset, Finset.mem_powersetCard, X]  tauto
See it in the graphDiscuss this resultChallenge it