perm_offset_avoiding_count_eq_sum_pie
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).
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|.
uses
Finset.card_image_of_injOnset 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
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.
uses
dif_pos,Finset.mem_image.mplet 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
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.
uses
Equiv.ofBijective,Subtype.mk.injEq,Subtype.ext,Finset.mem_image.mp,Finset.mem_image.mprlet 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)⟩)
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.
uses
Finset.mem_image.mpr,Equiv.extendSubtype_apply_of_memlet τ : 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
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}.
uses
Fintype.card_subtype,not_not.mp,Finset.mem_image.mp,Equiv.Perm.mul_apply,Finset.mem_image.mprrw [← 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 }
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|)!.
uses
Fintype.card_congr,Equiv.Perm.subtypeEquivSubtypePerm,Fintype.card_perm,Fintype.card_subtype,Finset.card_compl,Fintype.card_finrw [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]
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.
uses
Finset.mem_filter,Finset.mem_univ,true_and,Finset.filter_eq_empty_iffclassical 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
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.
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_sumhave 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
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.
uses
perm_offset_avoiding_count_eq_sum_pie_extend_card,Finset.filter_eq_empty_iff,Prod.exthave 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
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}.
uses
Finset.sum_congr,Finset.sum_filter,Finset.mem_filter.mp,Finset.card_image_of_injOn,Finset.card_le_univ,Finset.mem_rangerw [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
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.
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_powersetCardrw [← 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|)!.
- The helper lemma perm_offset_avoiding_count_eq_sum_pie_extend_card proves that extending a set of k non-attacking pairs to a permutation can be done in (n - k)! ways. While taken as standard on paper, the formal proof explicitly builds a bijection between the coordinate projections, extends it to a full permutation τ via Equiv.extendSubtype, and establishes a subtype bijection with permutations fixing the domain pointwise.
- The Principle of Inclusion-Exclusion is not invoked as a general library theorem; instead, it is proved inline in lines 82–107 by expressing the indicator [X ∩ Γ_π = ∅] as an alternating sum over subsets via Finset.sum_powerset_neg_one_pow_card and interchanging sums.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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