latin_double_three_tail_count_step
The number of tableaux of the next shape is the sum of availability permanents over all tableaux of the previous shape.
Statement
theorem latin_double_three_tail_count_step (k : ℕ) (hk : 5 ≤ k) : latin_tableaux_count (latin_double_three_tail_shape (k+1)) = ∑ T ∈ latin_tableaux (latin_double_three_tail_shape k), Matrix.permanent (latin_top_row_availability (latin_double_three_tail_shape k) T (k+1))- Source
- Helper for the open enumeration problem in https://arxiv.org/html/2610.29291v1, Conjecture 6.3, using the availability-permanent identity of Lemma 5.4. Exact computational route: experiments 4100, 4103 and 4106.
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 9
- latin_double_three_tail_shapeFor k at least 5, the Young diagram with row lengths (k,k-1,...,4,3,3). Its i-th row has length max(3,k-i) for i < k-1 and is empty…
- latin_tableauxFor a Young diagram μ, the set of Latin tableaux of shape μ and type μ' is the finset of fillings T from the cells of μ to natural numbers…
- latin_tableaux_countThe number of Latin tableaux of shape $\mu$ and type $\mu'$, denoted $LT(\mu)$, is the cardinality of the finset of Latin tableaux of…
- latin_top_row_availabilityThe zero-one matrix whose row index is a prospective symbol minus one and whose column index is a column: an entry is one precisely when…
- latin_double_three_tail_shape_rowLen_succDeleting the top row of the shape at k+1 leaves the shape at k, with row indices shifted by one.
- latin_double_three_tail_profile_succInduction step for the double-3-tail staircase profile: for k >= 5, if every Latin tableau of shape (k,k-1,...,4,3,3) has the canonical…
- latin_double_three_tail_shape_rowLenThe row-length sanity formula for the staircase with two bottom rows of length three.
- mem_latin_double_three_tail_shapeA cell (i,j) belongs to the double-3-tail shape exactly when i < k-1 and j < max(3,k-i).
- latin_double_three_tail_profileThe proposed column profile: among the first three columns, two contain [1,k-1] and one contains [1,k-2] together with k; intermediate…
- Used by 1
- latin_double_three_tail_count_formulaThe open formula in arXiv:2610.29291 Conjecture 6.3: the number of Latin tableaux of shape (k,k-1,...,4,3,3) is 9 times 4 to the power k-3…
The proof, explained
The proof partitions the Latin tableaux of shape k + 1 by their restriction to shape k using fiberwise counting. For each tableau T of shape k, the fiber consists of all valid extensions to shape k + 1, which is shown to be in bijection with permutations of Fin (k + 1) that do not clash with T in any column. Finally, the count of such collision-avoiding permutations is identified with the permanent of the top-row availability matrix.
Any cell in row 0 of the shape k + 1 has column index strictly less than k + 1.
By mem_latin_double_three_tail_shape, a cell (i, j) in shape k + 1 satisfies j < max 3 (k + 1 - i). For row 0 (i = 0), Nat.sub_zero simplifies this to j < max 3 (k + 1). Since k ≥ 2, max_eq_right simplifies the maximum to k + 1, yielding j < k + 1.
uses
mem_latin_double_three_tail_shape,Nat.sub_zero,max_eq_righttheorem latin_double_three_tail_count_step_top_lt (k : ℕ) (hk : 2 ≤ k) (c : (latin_double_three_tail_shape (k + 1)).cells) (h0 : c.1.1 = 0) : c.1.2 < k + 1 := by have h := (mem_latin_double_three_tail_shape (k + 1) c.1.1 c.1.2).mp c.2 rw [h0, Nat.sub_zero, max_eq_right (by omega)] at h exact h.2
Shifting any cell in shape k + 1 with nonzero row index up by one row yields a cell in shape k.
By mem_latin_double_three_tail_shape, the cell has row index c.1 < k and column index c.2 < max 3 (k + 1 - c.1). Since c.1 ≠ 0, k - (c.1 - 1) = k + 1 - c.1, so the column bound matches that of shape k, and c.1 - 1 < k - 1 follows by linear arithmetic. This also provides the well-definedness for extending any tableau T of shape k by a row 0 permutation.
uses
mem_latin_double_three_tail_shapetheorem latin_double_three_tail_count_step_low_mem (k : ℕ) (c : (latin_double_three_tail_shape (k + 1)).cells) (h0 : c.1.1 ≠ 0) : (c.1.1 - 1, c.1.2) ∈ (latin_double_three_tail_shape k).cells := by have h := (mem_latin_double_three_tail_shape (k + 1) c.1.1 c.1.2).mp c.2 apply (mem_latin_double_three_tail_shape k (c.1.1 - 1) c.1.2).mpr have : k - (c.1.1 - 1) = k + 1 - c.1.1 := by omega rw [this] exact ⟨by omega, h.2⟩ def latin_double_three_tail_count_step_ext (k : ℕ) (hk : 2 ≤ k) (T : (latin_double_three_tail_shape k).cells → ℕ) (σ : Equiv.Perm (Fin (k + 1))) : (latin_double_three_tail_shape (k + 1)).cells → ℕ := fun c => if h : c.1.1 = 0 then (σ ⟨c.1.2, latin_double_three_tail_count_step_top_lt k hk c h⟩).val + 1 else T ⟨(c.1.1 - 1, c.1.2), latin_double_three_tail_count_step_low_mem k c h⟩
Row 0 of shape k + 1 has length k + 1.
Evaluating the row length formula via latin_double_three_tail_shape_rowLen, row 0 has length max 3 (k + 1 - 0) by if_pos because 0 < k. Since k ≥ 2, max_eq_right evaluates this maximum to k + 1.
uses
latin_double_three_tail_shape_rowLen,if_pos,max_eq_righttheorem latin_double_three_tail_count_step_row0 (k : ℕ) (hk : 2 ≤ k) : (latin_double_three_tail_shape (k + 1)).rowLen 0 = k + 1 := by rw [latin_double_three_tail_shape_rowLen, if_pos (by omega)] exact max_eq_right (by omega)
In any Latin tableau of shape k + 1, the entries in row 0 are integers between 1 and k + 1.
By definition of a Latin tableau, each cell's value lies in the interval from 1 to the length of its row. For row 0, latin_double_three_tail_count_step_row0 shows the row length is k + 1, so Finset.mem_Icc implies the entry at (0, j) satisfies 1 ≤ T'(0, j) ≤ k + 1.
uses
latin_double_three_tail_profile_succ_top_mem,latin_double_three_tail_count_step_row0,Finset.mem_Icctheorem latin_double_three_tail_count_step_top_bound (k : ℕ) (hk : 2 ≤ k) (T' : (latin_double_three_tail_shape (k + 1)).cells → ℕ) (hT : T' ∈ latin_tableaux (latin_double_three_tail_shape (k + 1))) (j : ℕ) (hj : j < k + 1) : 1 ≤ T' ⟨(0, j), latin_double_three_tail_profile_succ_top_mem k j (by omega) hj⟩ ∧ T' ⟨(0, j), latin_double_three_tail_profile_succ_top_mem k j (by omega) hj⟩ ≤ k + 1 := by simp only [latin_tableaux, Finset.mem_filter, Fintype.mem_piFinset] at hT have h := hT.1 ⟨(0, j), latin_double_three_tail_profile_succ_top_mem k j (by omega) hj⟩ simp only [latin_double_three_tail_count_step_row0 k hk, Finset.mem_Icc] at h exact h
The entries in row 0 of a Latin tableau of shape k + 1 define a permutation of Fin (k + 1).
We define a function sending j to T'(0, j) - 1, which lies in Fin (k + 1) by latin_double_three_tail_count_step_top_bound. Row injectivity of the tableau implies that equal values must come from the same column, so the function is injective via Fin.ext and Fin.mk.injEq. On a finite type, injectivity is equivalent to bijectivity by Finite.injective_iff_bijective.mp, yielding a permutation via Equiv.ofBijective.
uses
latin_double_three_tail_profile_succ_top_mem,latin_double_three_tail_count_step_top_bound,Finite.injective_iff_bijective.mp,Fin.mk.injEq,Fin.extnoncomputable def latin_double_three_tail_count_step_perm (k : ℕ) (hk : 2 ≤ k) (T' : (latin_double_three_tail_shape (k + 1)).cells → ℕ) (hT : T' ∈ latin_tableaux (latin_double_three_tail_shape (k + 1))) : Equiv.Perm (Fin (k + 1)) := Equiv.ofBijective (fun j => ⟨T' ⟨(0, j.val), latin_double_three_tail_profile_succ_top_mem k j.val (by omega) j.isLt⟩ - 1, by have := latin_double_three_tail_count_step_top_bound k hk T' hT j.val j.isLt; omega⟩) (Finite.injective_iff_bijective.mp (by intro a b hab simp only [Fin.mk.injEq] at hab have ha := latin_double_three_tail_count_step_top_bound k hk T' hT a.val a.isLt have hb := latin_double_three_tail_count_step_top_bound k hk T' hT b.val b.isLt have heq : T' ⟨(0, a.val), latin_double_three_tail_profile_succ_top_mem k a.val (by omega) a.isLt⟩ = T' ⟨(0, b.val), latin_double_three_tail_profile_succ_top_mem k b.val (by omega) b.isLt⟩ := by omega simp only [latin_tableaux, Finset.mem_filter] at hT exact Fin.ext (hT.2.1 ⟨(0, a.val), latin_double_three_tail_profile_succ_top_mem k a.val (by omega) a.isLt⟩ ⟨(0, b.val), latin_double_three_tail_profile_succ_top_mem k b.val (by omega) b.isLt⟩ rfl heq)))
The value of the extracted permutation at column j plus 1 recovers the tableau entry T'(0, j).
Unfolding the definition of the permutation and using Equiv.ofBijective_apply, the permutation value is T'(0, j) - 1. Adding 1 and using the lower bound 1 ≤ T'(0, j) from latin_double_three_tail_count_step_top_bound recovers T'(0, j) by linear arithmetic.
uses
latin_double_three_tail_count_step_top_bound,Equiv.ofBijective_applytheorem latin_double_three_tail_count_step_perm_apply (k : ℕ) (hk : 2 ≤ k) (T' : (latin_double_three_tail_shape (k + 1)).cells → ℕ) (hT : T' ∈ latin_tableaux (latin_double_three_tail_shape (k + 1))) (j : Fin (k + 1)) : ((latin_double_three_tail_count_step_perm k hk T' hT j).val : ℕ) + 1 = T' ⟨(0, j.val), latin_double_three_tail_profile_succ_top_mem k j.val (by omega) j.isLt⟩ := by have := latin_double_three_tail_count_step_top_bound k hk T' hT j.val j.isLt simp only [latin_double_three_tail_count_step_perm, Equiv.ofBijective_apply] omega
Setup of the bijection between tableaux of shape k + 1 restricting to T and permutations avoiding column collisions with T.
We apply Finset.card_bij' with the forward map extracting the row 0 permutation via latin_double_three_tail_count_step_perm and the backward map extending T by a permutation σ via latin_double_three_tail_count_step_ext.
uses
Finset.card_bij'theorem latin_double_three_tail_count_step_fiber (k : ℕ) (hk : 2 ≤ k) (T : (latin_double_three_tail_shape k).cells → ℕ) (hT : T ∈ latin_tableaux (latin_double_three_tail_shape k)) : ((latin_tableaux (latin_double_three_tail_shape (k + 1))).filter (fun T' => latin_double_three_tail_profile_succ_restrict k T' = T)).card = (Finset.univ.filter (fun σ : Equiv.Perm (Fin (k + 1)) => ∀ j : Fin (k + 1), ∀ c : (latin_double_three_tail_shape k).cells, c.val.2 = j.val → T c ≠ (σ j).val + 1)).card := by have hT' := hT simp only [latin_tableaux, Finset.mem_filter, Fintype.mem_piFinset] at hT' obtain ⟨hb, hr, hcl⟩ := hT' refine Finset.card_bij' (fun T' h => latin_double_three_tail_count_step_perm k hk T' (Finset.mem_filter.mp h).1) (fun σ _ => latin_double_three_tail_count_step_ext k hk T σ) (hi := ?_) (hj := ?_) (left_inv := ?_) (right_inv := ?_)
The permutation extracted from an extending tableau T' has no column collisions with T.
If σ(j) + 1 equaled T(c) for some cell c in column j, then by latin_double_three_tail_count_step_perm_apply and the restriction hypothesis, T'(0, j) would equal T'(c.1 + 1, j). This contradicts column injectivity of T' because row 0 and row c.1 + 1 are distinct, completing the forward direction using true_and.
uses
latin_double_three_tail_count_step_perm_apply,true_and· intro T' h obtain ⟨hT1, hres⟩ := Finset.mem_filter.mp h simp only [Finset.mem_filter, Finset.mem_univ, true_and] intro j c hcj heq rw [latin_double_three_tail_count_step_perm_apply] at heq rw [← hres] at heq have hT1' := hT1 simp only [latin_tableaux, Finset.mem_filter] at hT1' have := hT1'.2.2 _ _ hcj heq simp at this
Extending T by a non-conflicting permutation σ yields a valid Latin tableau of shape k + 1.
In row 0, entries (σ(j) : ℕ) + 1 satisfy the row length bound k + 1 by latin_double_three_tail_count_step_row0 and Finset.mem_Icc. In lower rows, entries come from T and satisfy the row bounds using latin_double_three_tail_shape_rowLen_succ and Nat.sub_add_cancel. Row injectivity follows from injectivity of σ on row 0 via Fin.ext and from T on lower rows. Column injectivity holds because σ avoids all values appearing in T in each column, and within lower rows it follows from column injectivity of T, handling cases using dif_pos and dif_neg together with latin_double_three_tail_count_step_top_lt and latin_double_three_tail_count_step_low_mem.
uses
latin_double_three_tail_count_step_row0,latin_double_three_tail_count_step_top_lt,latin_double_three_tail_count_step_low_mem,latin_double_three_tail_shape_rowLen_succ,Nat.sub_add_cancel,dif_pos,dif_neg,Fin.ext,Finset.mem_Icc· intro σ hσ have hσ := (Finset.mem_filter.mp hσ).2 refine Finset.mem_filter.mpr ⟨?_, ?_⟩ · simp only [latin_tableaux, Finset.mem_filter, Fintype.mem_piFinset] refine ⟨fun c => ?_, fun c1 c2 h1 h2 => ?_, fun c1 c2 h1 h2 => ?_⟩ · simp only [latin_double_three_tail_count_step_ext] split_ifs with h0 · rw [Finset.mem_Icc, h0, latin_double_three_tail_count_step_row0 k hk] exact ⟨by omega, by have := (σ ⟨c.1.2, latin_double_three_tail_count_step_top_lt k hk c h0⟩).isLt; omega⟩ · have := hb ⟨(c.1.1 - 1, c.1.2), latin_double_three_tail_count_step_low_mem k c h0⟩ have e2 : (latin_double_three_tail_shape (k + 1)).rowLen c.1.1 = (latin_double_three_tail_shape k).rowLen (c.1.1 - 1) := by have := latin_double_three_tail_shape_rowLen_succ k (c.1.1 - 1) rwa [Nat.sub_add_cancel (by omega)] at this rw [e2] exact this · simp only [latin_double_three_tail_count_step_ext] at h2 by_cases h0 : c1.1.1 = 0 · have h0' : c2.1.1 = 0 := by omega rw [dif_pos h0, dif_pos h0'] at h2 have := σ.injective (Fin.ext (by simpa using h2)) simpa using this · have h0' : c2.1.1 ≠ 0 := by omega rw [dif_neg h0, dif_neg h0'] at h2 exact hr _ _ (by simp [h1]) h2 · simp only [latin_double_three_tail_count_step_ext] at h2 by_cases h0 : c1.1.1 = 0 <;> by_cases h0' : c2.1.1 = 0 · omega · rw [dif_pos h0, dif_neg h0'] at h2 exact absurd h2.symm (hσ ⟨c1.1.2, latin_double_three_tail_count_step_top_lt k hk c1 h0⟩ _ (by simp [h1])) · rw [dif_neg h0, dif_pos h0'] at h2 exact absurd h2 (hσ ⟨c2.1.2, latin_double_three_tail_count_step_top_lt k hk c2 h0'⟩ _ (by simp [h1])) · rw [dif_neg h0, dif_neg h0'] at h2 have := hcl _ _ (by simp [h1]) h2 simp at this omega
The restriction of the extended tableau back to shape k recovers T.
For any cell c of shape k, its restriction evaluates the extended tableau at (c.1 + 1, c.2). Since the row index c.1 + 1 is nonzero, the extension evaluates to T(c.1 + 1 - 1, c.2) = T(c) by dif_neg.
uses
dif_neg· funext c simp only [latin_double_three_tail_profile_succ_restrict, latin_double_three_tail_count_step_ext] rw [dif_neg (by simp)] congr 1
The forward and backward maps between extending tableaux and non-conflicting permutations are mutual inverses.
On the left, an extending tableau T' is reconstructed from its extracted permutation on row 0 via latin_double_three_tail_count_step_perm_apply and from its restriction T on lower rows, proving equality using Subtype.ext and Prod.ext. On the right, extracting the permutation from the extension of σ immediately recovers σ since (σ(j) + 1) - 1 = σ(j).
uses
latin_double_three_tail_count_step_perm_apply,Subtype.ext,Prod.ext· intro T' h obtain ⟨hT1, hres⟩ := Finset.mem_filter.mp h funext c simp only [latin_double_three_tail_count_step_ext] split_ifs with h0 · rw [latin_double_three_tail_count_step_perm_apply] congr 1 exact Subtype.ext (Prod.ext h0.symm rfl) · rw [← hres] simp only [latin_double_three_tail_profile_succ_restrict] congr 1 exact Subtype.ext (Prod.ext (by simp; omega) rfl) · intro σ hσ ext j simp [latin_double_three_tail_count_step_perm, latin_double_three_tail_count_step_ext]
The total count of tableaux of shape k + 1 is the sum over tableaux T of shape k of the sizes of their extension fibers.
Unfolding latin_tableaux_count, we partition the tableaux of shape k + 1 according to their restriction to shape k using Finset.card_eq_sum_card_fiberwise and latin_double_three_tail_profile_succ_restrict_mem. We then apply Finset.sum_congr to equate each summand with the fiber size, noting latin_double_three_tail_profile_succ.
uses
latin_double_three_tail_profile_succ,Finset.card_eq_sum_card_fiberwise,latin_double_three_tail_profile_succ_restrict_mem,Finset.sum_congrtheorem latin_double_three_tail_count_step (k : ℕ) (hk : 5 ≤ k) : latin_tableaux_count (latin_double_three_tail_shape (k+1)) = ∑ T ∈ latin_tableaux (latin_double_three_tail_shape k), Matrix.permanent (latin_top_row_availability (latin_double_three_tail_shape k) T (k+1)) := by have _hsucc := @latin_double_three_tail_profile_succ unfold latin_tableaux_count rw [Finset.card_eq_sum_card_fiberwise (f := latin_double_three_tail_profile_succ_restrict k) (t := latin_tableaux (latin_double_three_tail_shape k)) (fun T' hT' => latin_double_three_tail_profile_succ_restrict_mem k T' hT')] refine Finset.sum_congr rfl fun T hT => ?_
For each tableau T of shape k, its fiber size equals the permanent of the top-row availability matrix.
By latin_double_three_tail_count_step_fiber, the fiber size is the number of permutations avoiding column collisions with T, which Finset.card_filter writes as a sum of 0-1 indicators. Unfolding Matrix.permanent and latin_top_row_availability, the permanent is the sum over permutations of the product of column availability indicators. By Finset.prod_boole, this product equals 1 precisely when σ avoids collisions in all columns, matching the fiber indicator; simplifying with Finset.mem_univ and true_imp_iff completes the proof.
uses
latin_double_three_tail_count_step_fiber,Finset.card_filter,Finset.sum_congr,Finset.prod_boole,Finset.mem_univ,true_imp_iffrw [latin_double_three_tail_count_step_fiber k (by omega) T hT, Finset.card_filter] unfold Matrix.permanent latin_top_row_availability refine Finset.sum_congr rfl fun σ _ => ?_ rw [Finset.prod_boole] simp only [Finset.mem_univ, true_imp_iff]
Equiv.ofBijective_apply- Evaluating an equivalence constructed from a bijection yields the same result as applying the underlying function.
Fin.ext- Two elements of Fin n are equal if their underlying natural values are equal.
Fin.mk.injEq- Two elements of Fin n constructed from underlying naturals are equal if and only if those naturals are equal.
Finset.card_bij'- Two finite sets have equal cardinality if there exist maps between them that are mutual inverses on the respective sets.
Finset.card_eq_sum_card_fiberwise- The cardinality of a finite set is the sum of the cardinalities of its fibers under a map to another finite set.
Finset.card_filter- The number of elements in a finite set satisfying a predicate equals the sum over the set of the predicate's 0-1 indicator function.
Finset.mem_Icc- An integer belongs to the closed interval [a, b] if and only if a ≤ x ≤ b.
Finset.mem_univ- Every element of a finite type belongs to the universal finset Finset.univ.
Finset.prod_boole- A finite product of 0-1 indicators equals 1 if the condition holds for every element in the index set, and 0 otherwise.
Finset.sum_congr- Two finite sums are equal if their index sets are identical and their summands agree at every index.
Finite.injective_iff_bijective.mp- An injective endofunction on a finite type is bijective.
Nat.sub_zero- Subtracting zero from a natural number leaves it unchanged (n - 0 = n).
Nat.sub_add_cancel- If m ≤ n, then (n - m) + m = n.
dif_neg- A dependent if-then-else expression reduces to its else branch when the condition is false.
dif_pos- A dependent if-then-else expression reduces to its then branch when the condition is true.
if_pos- A conditional expression evaluates to its then branch when the condition is true.
latin_double_three_tail_count_step_fiber- The number of Latin tableaux of shape k + 1 restricting to a fixed tableau T of shape k equals the number of permutations of Fin (k + 1) that do not clash with T in any column.
latin_double_three_tail_count_step_low_mem- If a cell in latin_double_three_tail_shape (k + 1) has nonzero row index, decrementing its row index produces a valid cell in latin_double_three_tail_shape k.
latin_double_three_tail_count_step_perm_apply- The value of the permutation induced by a tableau of shape k + 1 at column j, plus 1, equals the entry at (0, j) in the tableau.
latin_double_three_tail_count_step_row0- For k ≥ 2, row 0 of latin_double_three_tail_shape (k + 1) has length k + 1.
latin_double_three_tail_count_step_top_bound- In any Latin tableau of shape k + 1 with k ≥ 2, every entry in row 0 lies between 1 and k + 1.
latin_double_three_tail_count_step_top_lt- For k ≥ 2, any cell in row 0 of latin_double_three_tail_shape (k + 1) has column index strictly less than k + 1.
latin_double_three_tail_profile_succ- If all Latin tableaux of shape k satisfy the profile property, then all Latin tableaux of shape k + 1 do as well.
latin_double_three_tail_profile_succ_restrict_mem- Restricting a Latin tableau of shape k + 1 by dropping row 0 yields a valid Latin tableau of shape k.
latin_double_three_tail_profile_succ_top_mem- For k ≥ 1 and j < k + 1, the cell (0, j) belongs to latin_double_three_tail_shape (k + 1).
latin_double_three_tail_shape_rowLen- The length of row i in latin_double_three_tail_shape k is max 3 (k - i) if i < k - 1, and 0 otherwise.
latin_double_three_tail_shape_rowLen_succ- The length of row i + 1 in latin_double_three_tail_shape (k + 1) equals the length of row i in latin_double_three_tail_shape k.
max_eq_right- If a ≤ b, then max a b = b.
mem_latin_double_three_tail_shape- A pair (i, j) belongs to latin_double_three_tail_shape k if and only if i < k - 1 and j < max 3 (k - i).
Prod.ext- Two ordered pairs are equal if their first components are equal and their second components are equal.
Subtype.ext- Two subtype elements are equal if their underlying values are equal.
true_and- The logical proposition True ∧ p is equivalent to p.
true_imp_iff- The implication True → p is equivalent to p.
- Linear inequalities and coordinate bounds throughout the helper lemmas and case analyses are discharged by the `omega` decision procedure.
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.
theorem latin_double_three_tail_count_step_top_lt (k : ℕ) (hk : 2 ≤ k) (c : (latin_double_three_tail_shape (k + 1)).cells) (h0 : c.1.1 = 0) : c.1.2 < k + 1 := by have h := (mem_latin_double_three_tail_shape (k + 1) c.1.1 c.1.2).mp c.2 rw [h0, Nat.sub_zero, max_eq_right (by omega)] at h exact h.2theorem latin_double_three_tail_count_step_low_mem (k : ℕ) (c : (latin_double_three_tail_shape (k + 1)).cells) (h0 : c.1.1 ≠ 0) : (c.1.1 - 1, c.1.2) ∈ (latin_double_three_tail_shape k).cells := by have h := (mem_latin_double_three_tail_shape (k + 1) c.1.1 c.1.2).mp c.2 apply (mem_latin_double_three_tail_shape k (c.1.1 - 1) c.1.2).mpr have : k - (c.1.1 - 1) = k + 1 - c.1.1 := by omega rw [this] exact ⟨by omega, h.2⟩def latin_double_three_tail_count_step_ext (k : ℕ) (hk : 2 ≤ k) (T : (latin_double_three_tail_shape k).cells → ℕ) (σ : Equiv.Perm (Fin (k + 1))) : (latin_double_three_tail_shape (k + 1)).cells → ℕ := fun c => if h : c.1.1 = 0 then (σ ⟨c.1.2, latin_double_three_tail_count_step_top_lt k hk c h⟩).val + 1 else T ⟨(c.1.1 - 1, c.1.2), latin_double_three_tail_count_step_low_mem k c h⟩theorem latin_double_three_tail_count_step_row0 (k : ℕ) (hk : 2 ≤ k) : (latin_double_three_tail_shape (k + 1)).rowLen 0 = k + 1 := by rw [latin_double_three_tail_shape_rowLen, if_pos (by omega)] exact max_eq_right (by omega)theorem latin_double_three_tail_count_step_top_bound (k : ℕ) (hk : 2 ≤ k) (T' : (latin_double_three_tail_shape (k + 1)).cells → ℕ) (hT : T' ∈ latin_tableaux (latin_double_three_tail_shape (k + 1))) (j : ℕ) (hj : j < k + 1) : 1 ≤ T' ⟨(0, j), latin_double_three_tail_profile_succ_top_mem k j (by omega) hj⟩ ∧ T' ⟨(0, j), latin_double_three_tail_profile_succ_top_mem k j (by omega) hj⟩ ≤ k + 1 := by simp only [latin_tableaux, Finset.mem_filter, Fintype.mem_piFinset] at hT have h := hT.1 ⟨(0, j), latin_double_three_tail_profile_succ_top_mem k j (by omega) hj⟩ simp only [latin_double_three_tail_count_step_row0 k hk, Finset.mem_Icc] at h exact hnoncomputable def latin_double_three_tail_count_step_perm (k : ℕ) (hk : 2 ≤ k) (T' : (latin_double_three_tail_shape (k + 1)).cells → ℕ) (hT : T' ∈ latin_tableaux (latin_double_three_tail_shape (k + 1))) : Equiv.Perm (Fin (k + 1)) := Equiv.ofBijective (fun j => ⟨T' ⟨(0, j.val), latin_double_three_tail_profile_succ_top_mem k j.val (by omega) j.isLt⟩ - 1, by have := latin_double_three_tail_count_step_top_bound k hk T' hT j.val j.isLt; omega⟩) (Finite.injective_iff_bijective.mp (by intro a b hab simp only [Fin.mk.injEq] at hab have ha := latin_double_three_tail_count_step_top_bound k hk T' hT a.val a.isLt have hb := latin_double_three_tail_count_step_top_bound k hk T' hT b.val b.isLt have heq : T' ⟨(0, a.val), latin_double_three_tail_profile_succ_top_mem k a.val (by omega) a.isLt⟩ = T' ⟨(0, b.val), latin_double_three_tail_profile_succ_top_mem k b.val (by omega) b.isLt⟩ := by omega simp only [latin_tableaux, Finset.mem_filter] at hT exact Fin.ext (hT.2.1 ⟨(0, a.val), latin_double_three_tail_profile_succ_top_mem k a.val (by omega) a.isLt⟩ ⟨(0, b.val), latin_double_three_tail_profile_succ_top_mem k b.val (by omega) b.isLt⟩ rfl heq)))theorem latin_double_three_tail_count_step_perm_apply (k : ℕ) (hk : 2 ≤ k) (T' : (latin_double_three_tail_shape (k + 1)).cells → ℕ) (hT : T' ∈ latin_tableaux (latin_double_three_tail_shape (k + 1))) (j : Fin (k + 1)) : ((latin_double_three_tail_count_step_perm k hk T' hT j).val : ℕ) + 1 = T' ⟨(0, j.val), latin_double_three_tail_profile_succ_top_mem k j.val (by omega) j.isLt⟩ := by have := latin_double_three_tail_count_step_top_bound k hk T' hT j.val j.isLt simp only [latin_double_three_tail_count_step_perm, Equiv.ofBijective_apply] omegatheorem latin_double_three_tail_count_step_fiber (k : ℕ) (hk : 2 ≤ k) (T : (latin_double_three_tail_shape k).cells → ℕ) (hT : T ∈ latin_tableaux (latin_double_three_tail_shape k)) : ((latin_tableaux (latin_double_three_tail_shape (k + 1))).filter (fun T' => latin_double_three_tail_profile_succ_restrict k T' = T)).card = (Finset.univ.filter (fun σ : Equiv.Perm (Fin (k + 1)) => ∀ j : Fin (k + 1), ∀ c : (latin_double_three_tail_shape k).cells, c.val.2 = j.val → T c ≠ (σ j).val + 1)).card := by have hT' := hT simp only [latin_tableaux, Finset.mem_filter, Fintype.mem_piFinset] at hT' obtain ⟨hb, hr, hcl⟩ := hT' refine Finset.card_bij' (fun T' h => latin_double_three_tail_count_step_perm k hk T' (Finset.mem_filter.mp h).1) (fun σ _ => latin_double_three_tail_count_step_ext k hk T σ) (hi := ?_) (hj := ?_) (left_inv := ?_) (right_inv := ?_) · intro T' h obtain ⟨hT1, hres⟩ := Finset.mem_filter.mp h simp only [Finset.mem_filter, Finset.mem_univ, true_and] intro j c hcj heq rw [latin_double_three_tail_count_step_perm_apply] at heq rw [← hres] at heq have hT1' := hT1 simp only [latin_tableaux, Finset.mem_filter] at hT1' have := hT1'.2.2 _ _ hcj heq simp at this · intro σ hσ have hσ := (Finset.mem_filter.mp hσ).2 refine Finset.mem_filter.mpr ⟨?_, ?_⟩ · simp only [latin_tableaux, Finset.mem_filter, Fintype.mem_piFinset] refine ⟨fun c => ?_, fun c1 c2 h1 h2 => ?_, fun c1 c2 h1 h2 => ?_⟩ · simp only [latin_double_three_tail_count_step_ext] split_ifs with h0 · rw [Finset.mem_Icc, h0, latin_double_three_tail_count_step_row0 k hk] exact ⟨by omega, by have := (σ ⟨c.1.2, latin_double_three_tail_count_step_top_lt k hk c h0⟩).isLt; omega⟩ · have := hb ⟨(c.1.1 - 1, c.1.2), latin_double_three_tail_count_step_low_mem k c h0⟩ have e2 : (latin_double_three_tail_shape (k + 1)).rowLen c.1.1 = (latin_double_three_tail_shape k).rowLen (c.1.1 - 1) := by have := latin_double_three_tail_shape_rowLen_succ k (c.1.1 - 1) rwa [Nat.sub_add_cancel (by omega)] at this rw [e2] exact this · simp only [latin_double_three_tail_count_step_ext] at h2 by_cases h0 : c1.1.1 = 0 · have h0' : c2.1.1 = 0 := by omega rw [dif_pos h0, dif_pos h0'] at h2 have := σ.injective (Fin.ext (by simpa using h2)) simpa using this · have h0' : c2.1.1 ≠ 0 := by omega rw [dif_neg h0, dif_neg h0'] at h2 exact hr _ _ (by simp [h1]) h2 · simp only [latin_double_three_tail_count_step_ext] at h2 by_cases h0 : c1.1.1 = 0 <;> by_cases h0' : c2.1.1 = 0 · omega · rw [dif_pos h0, dif_neg h0'] at h2 exact absurd h2.symm (hσ ⟨c1.1.2, latin_double_three_tail_count_step_top_lt k hk c1 h0⟩ _ (by simp [h1])) · rw [dif_neg h0, dif_pos h0'] at h2 exact absurd h2 (hσ ⟨c2.1.2, latin_double_three_tail_count_step_top_lt k hk c2 h0'⟩ _ (by simp [h1])) · rw [dif_neg h0, dif_neg h0'] at h2 have := hcl _ _ (by simp [h1]) h2 simp at this omega · funext c simp only [latin_double_three_tail_profile_succ_restrict, latin_double_three_tail_count_step_ext] rw [dif_neg (by simp)] congr 1 · intro T' h obtain ⟨hT1, hres⟩ := Finset.mem_filter.mp h funext c simp only [latin_double_three_tail_count_step_ext] split_ifs with h0 · rw [latin_double_three_tail_count_step_perm_apply] congr 1 exact Subtype.ext (Prod.ext h0.symm rfl) · rw [← hres] simp only [latin_double_three_tail_profile_succ_restrict] congr 1 exact Subtype.ext (Prod.ext (by simp; omega) rfl) · intro σ hσ ext j simp [latin_double_three_tail_count_step_perm, latin_double_three_tail_count_step_ext]theorem latin_double_three_tail_count_step (k : ℕ) (hk : 5 ≤ k) : latin_tableaux_count (latin_double_three_tail_shape (k+1)) = ∑ T ∈ latin_tableaux (latin_double_three_tail_shape k), Matrix.permanent (latin_top_row_availability (latin_double_three_tail_shape k) T (k+1)) := by have _hsucc := @latin_double_three_tail_profile_succ unfold latin_tableaux_count rw [Finset.card_eq_sum_card_fiberwise (f := latin_double_three_tail_profile_succ_restrict k) (t := latin_tableaux (latin_double_three_tail_shape k)) (fun T' hT' => latin_double_three_tail_profile_succ_restrict_mem k T' hT')] refine Finset.sum_congr rfl fun T hT => ?_ rw [latin_double_three_tail_count_step_fiber k (by omega) T hT, Finset.card_filter] unfold Matrix.permanent latin_top_row_availability refine Finset.sum_congr rfl fun σ _ => ?_ rw [Finset.prod_boole] simp only [Finset.mem_univ, true_imp_iff]