The Number of Latin Tableaux of Shape $(k, k-1, \dots, 4, 3, 3)$ is $9 \cdot 4^{k-3}$ for Every $k \ge 5$
medium tier2026-10-28OP-512reviewed by Claude Code中文版
Abstract
Latin tableaux generalize Latin squares to Young diagrams. In arXiv:2610.29291, Conjecture 6.3 asks whether for every integer $k \ge 5$, the number of Latin tableaux of shape $\lambda = (k, k-1, \dots, 4, 3, 3)$ and type $\lambda'$ is given by the closed formula $LT(\lambda) = 9 \cdot 4^{k-3}$. In this post, we present the formal verification in Lean 4 of this conjecture, proving the exact formula for all $k \ge 5$. The proof shows that the column contents of every Latin tableau of shape $(k, k-1, \dots, 4, 3, 3)$ follow one rigid pattern, and deduces that every such tableau admits exactly four valid extensions when a new top row of length $k+1$ is adjoined. Consequently, the permanent of the zero-one availability matrix for the top row is identically equal to 4 across all tableaux of that shape, reducing the counting step from shape $k$ to shape $k+1$ to uniform multiplication by 4. Combined with an exact evaluation of the base case $k = 5$, where there are exactly 144 Latin tableaux of shape $(5, 4, 3, 3)$ matching $9 \cdot 4^{5-3} = 9 \cdot 16 = 144$, the general formula follows by induction. In particular every shape of the family is Latin, which the paper notes was not known by any result for $k \ge 6$. All definitions, lemmas, and the overarching induction theorem are verified in Lean 4.
1. Introduction
A Latin tableau is a filling of a Young diagram whose entries satisfy Latin properties along its rows and columns. Specifically, for a partition $\mu$, a Latin tableau of shape $\mu$ and type $\mu'$ is a filling of the cells of $\mu$ with positive integers such that the entries in each row $i$ are chosen from $\{1, \dots, \mu_i\}$ without repetition, and no positive integer appears more than once in any column. Since row $i$ contains exactly $\mu_i$ cells, the distinctness condition implies that each row $i$ is filled with a permutation of the set $\{1, 2, \dots, \mu_i\}$. When the Young diagram is a square of size $n \times n$, these structures correspond to standard Latin squares of order $n$. For non-rectangular diagrams, the interaction between row-length bounds and column distinctness constraints introduces intricate combinatorial dependencies.
The study of Latin tableaux and their exact enumeration for infinite families of shapes was investigated in arXiv:2610.29291. Among the partition families considered in that work are staircase diagrams and staircase-like shapes with modified tails. A specific family of shapes consists of those with a double-three staircase tail: for an integer $k \ge 5$, the partition $\lambda$ is defined by the sequence of row lengths $$\lambda = (k, k-1, \dots, 4, 3, 3).$$ This diagram has $k-1$ nonempty rows: the first row has length $k$, each subsequent row decreases in length by 1 until length 3 is reached, and the final two rows both have length 3.
In arXiv:2610.29291, Conjecture 6.3 posed the question of whether the number of Latin tableaux of shape $\lambda = (k, k-1, \dots, 4, 3, 3)$ and type $\lambda'$, denoted by $LT(\lambda)$, is given by the exact exponential formula $$LT(k, k-1, \dots, 4, 3, 3) = 9 \cdot 4^{k-3}$$ for every integer $k \ge 5$. For the smallest parameter value $k = 5$, the partition is $(5, 4, 3, 3)$, and the conjectured formula predicts $9 \cdot 4^{5-3} = 9 \cdot 16 = 144$ Latin tableaux. The paper reports 576 tableaux for $k = 6$, in agreement with the formula, observes that every filling of $(6,5,4,3,3)$ has $4$, $5$, $6$ in the first three cells of the top row and $1$, $2$, $3$ in the last three, and notes that no shape of the family with $k \ge 6$ was known to be Latin by any result.
The difficulty in establishing such an enumeration directly lies in the recursive nature of Young diagram extensions. Adding a new top row of length $k+1$ above a tableau of shape $(k, k-1, \dots, 4, 3, 3)$ requires placing a permutation of $\{1, 2, \dots, k+1\}$ such that no entry conflicts with any entry already present in the same column. In general, the number of ways to complete such a row depends on the specific entries appearing in the columns of the underlying tableau $T$. The count of completions for a given tableau $T$ can be expressed as the permanent of a $(k+1) \times (k+1)$ zero-one matrix, known as the top-row availability matrix. Because matrix permanents can vary across different tableaux of the same shape, sums of permanents over large sets of tableaux typically resist closed-form simplification unless strong structural uniformity is present.
In this post, we report on the complete formal resolution of Conjecture 6.3 in Lean 4 via the theorem latin_double_three_tail_count_formula. The proof first establishes a rigid column pattern shared by all tableaux of the family, and from it a structural regularity: for every integer $k \ge 5$, every Latin tableau of shape $(k, k-1, \dots, 4, 3, 3)$ admits exactly four valid extensions to a Latin tableau of shape $(k+1, k, \dots, 4, 3, 3)$. That is, the permanent of the availability matrix is not merely 4 on average; it is pointwise invariant, equal to 4 for every single tableau in the family. This pointwise extension property turns the summation over all tableaux into a scalar multiplication by 4, reducing the inductive step to an elementary recurrence. With the base case $k = 5$ formally established, the closed formula $9 \cdot 4^{k-3}$ holds for all $k \ge 5$.
2. Preliminaries
To formalize the enumeration in Lean 4, we define Young diagrams, the family of double-three tail partitions, the set of Latin tableaux, and the top-row availability matrix. We adhere to the mathematical and Lean structures provided in the library.
A Young diagram $\mu$ is represented as a collection of cells $(i, j) \in \mathbb{N} \times \mathbb{N}$ arranged in rows and columns, where $i$ denotes the row index and $j$ denotes the column index. In the Lean formalization, both row and column indices are 0-indexed, so the top-left cell of the diagram is $(0, 0)$. The length of row $i$ is denoted by $\mu.\text{rowLen}(i)$.
Definition 1 (latin_double_three_tail_shape). For an integer $k \ge 5$, the Young diagram with a double-three staircase tail, denoted $\lambda(k)$, is the partition whose $i$-th row length for $0 \le i < k-1$ is given by $$\lambda(k).\text{rowLen}(i) = \max(3, k - i),$$ and whose rows are empty for all $i \ge k-1$. In sequence notation, the row lengths of $\lambda(k)$ are $$(k, k-1, k-2, \dots, 4, 3, 3),$$ comprising exactly $k-1$ nonempty rows. For example, when $k = 5$, the diagram $\lambda(5)$ has row lengths $(5, 4, 3, 3)$. For $k = 6$, the row lengths are $(6, 5, 4, 3, 3)$.
Remark on indexing and empty rows. The Lean definition latin_double_three_tail_shape specifies row lengths using the 0-indexed formula $\max(3, k - i)$ strictly for $i < k - 1$. For all $i \ge k - 1$, the row length is implicitly 0. Thus, exactly $k - 1$ rows are nonempty. The final two nonempty rows, at indices $i = k - 3$ and $i = k - 2$, both have length $\max(3, 3) = 3$ and $\max(3, 2) = 3$, creating the double-three tail.
Definition 2 (latin_tableaux). Let $\mu$ be a Young diagram. A Latin tableau of shape $\mu$ and type $\mu'$ is a filling $T : \mu.\text{cells} \to \mathbb{N}$ satisfying the following conditions:
- Row-length bounds: For each cell $c = (i, j) \in \mu.\text{cells}$, the entry $T(c)$ belongs to the discrete interval $\{1, 2, \dots, \mu.\text{rowLen}(i)\}$.
- Row distinctness: For any two cells $c_1 = (i_1, j_1)$ and $c_2 = (i_2, j_2)$ in $\mu.\text{cells}$ with $i_1 = i_2$, if $T(c_1) = T(c_2)$, then $j_1 = j_2$.
- Column distinctness: For any two cells $c_1 = (i_1, j_1)$ and $c_2 = (i_2, j_2)$ in $\mu.\text{cells}$ with $j_1 = j_2$, if $T(c_1) = T(c_2)$, then $i_1 = i_2$.
The set of all such Latin tableaux on $\mu$ is denoted by latin_tableaux $\mu$.
Remark on row permutations. Because row $i$ contains exactly $\mu.\text{rowLen}(i)$ cells and each cell takes a value in $\{1, \dots, \mu.\text{rowLen}(i)\}$, the row injectivity condition guarantees that the sequence of entries in row $i$ is a permutation of $\{1, \dots, \mu.\text{rowLen}(i)\}$. In contrast, column lengths vary across the diagram, and the column condition requires that no symbol is repeated within any column.
Definition 3 (latin_tableaux_count). For a Young diagram $\mu$, the count of Latin tableaux of shape $\mu$ and type $\mu'$, denoted $LT(\mu)$, is the cardinality of the finset latin_tableaux $\mu$: $$LT(\mu) = \#(\text{latin\_tableaux}(\mu)).$$
Definition 4 (latin_top_row_availability). Let $d$ be a Young diagram, let $T \in \text{latin\_tableaux}(d)$, and let $w \in \mathbb{N}$ denote the width of a prospective top row to be added above $T$. The top-row availability matrix of $T$ for width $w$ is the $w \times w$ matrix over $\mathbb{N}$, denoted $A(d, T, w)$, defined for indices $i, j \in \{0, 1, \dots, w-1\}$ by $$A(d, T, w)_{i, j} = \begin{cases} 1 & \text{if for all } c \in d.\text{cells} \text{ with } c.\text{col} = j, \text{ we have } T(c) \neq i + 1, \\ 0 & \text{otherwise.} \end{cases}$$
Remark on prospective symbols and columns. In latin_top_row_availability, the matrix rows index prospective symbols $s = i + 1 \in \{1, \dots, w\}$, while the matrix columns index tableau columns $j \in \{0, \dots, w-1\}$. An entry is 1 precisely when placing symbol $i + 1$ into column $j$ creates no column conflict with any cell in column $j$ of $T$. A valid placement of a complete top row of length $w$ corresponds to a bijection between symbols and columns with availability 1, and the total number of such valid top rows is given by the permanent of $A(d, T, w)$.
3. Main result
The main theorem establishes the validity of Conjecture 6.3 from arXiv:2610.29291, giving an exact exponential formula for the number of Latin tableaux with a double-three staircase tail.
Theorem (latin_double_three_tail_count_formula). For every integer $k \ge 5$, the number of Latin tableaux of shape $\lambda(k) = (k, k-1, \dots, 4, 3, 3)$ and type $\lambda(k)'$ is given by $$LT(\lambda(k)) = 9 \cdot 4^{k-3}.$$
In Lean 4, the theorem is named latin_double_three_tail_count_formula. The statement takes a natural number $k$, assumes the hypothesis $5 \le k$, applies latin_double_three_tail_shape to construct the Young diagram, and asserts that latin_tableaux_count equals $9 \cdot 4^{k-3}$.
In addition to the main formula, the formal development provides three foundational results:
- Base-case enumeration (
latin_double_three_tail_count_base): For $k = 5$, the Young diagram has shape $(5, 4, 3, 3)$, and the number of Latin tableaux is exactly 144, verifying $9 \cdot 4^{5-3} = 9 \cdot 16 = 144$. - Inductive step formula (
latin_double_three_tail_count_step): For every $k \ge 5$, the number of Latin tableaux of shape $\lambda(k+1)$ equals the sum of the permanents of the top-row availability matrices over all Latin tableaux of shape $\lambda(k)$. - Pointwise four-extension property (
latin_double_three_tail_four_extensions): For every $k \ge 5$ and every Latin tableau $T$ of shape $\lambda(k)$, the permanent of the top-row availability matrix of width $k+1$ is identically equal to 4.
theorem latin_double_three_tail_count_formula (k : ℕ) (hk : 5 ≤ k) : latin_tableaux_count (latin_double_three_tail_shape k) = 9 * 4^(k-3)4. Proof
We present the proof of latin_double_three_tail_count_formula following the formal argument verified in Lean 4.
The idea of the proof is an induction on $k \ge 5$. The base case at $k = 5$ is verified by exhaustive computation on the finite set of tableaux of shape $(5, 4, 3, 3)$. For the inductive step, adjoining a row of length $k+1$ at the top of a tableau of shape $\lambda(k) = (k, k-1, \dots, 4, 3, 3)$ yields a tableau of shape $\lambda(k+1) = (k+1, k, \dots, 4, 3, 3)$. The number of ways to fill this top row without violating column distinctness equals the permanent of the availability matrix. Every tableau of shape $\lambda(k)$ has the same rigid pattern of column contents, and from it its availability permanent is identically equal to 4, so the sum of permanents factors into 4 times the cardinality of latin_tableaux of shape $\lambda(k)$. Applying the induction hypothesis reduces the step to elementary exponent arithmetic.
Lemma 1 (latin_double_three_tail_count_base). The number of Latin tableaux of shape $(5, 4, 3, 3)$ satisfies $$\text{latin\_tableaux\_count}(\text{latin\_double\_three\_tail\_shape } 5) = 144.$$
*Proof of Lemma 1.* The Young diagram $\lambda(5)$ has row lengths $(5, 4, 3, 3)$, which contain $5 + 4 + 3 + 3 = 15$ cells in total. A tableau is an assignment of values in $\{1, \dots, \lambda(5).\text{rowLen}(i)\}$ to each cell $(i, j)$ such that entries are distinct along each row and distinct along each column. Because the cell set is finite and the set of possible fillings is finite, Lean evaluates the cardinality of the filtered finset of Latin tableaux. The computation searches through all valid row permutations satisfying column injectivity across the 15 cells. The verification confirms that exactly 144 fillings satisfy all constraints. Noting that $9 \cdot 4^{5-3} = 9 \cdot 4^2 = 9 \cdot 16 = 144$, the base case holds.
Lemma 2 (latin_double_three_tail_count_step). For any integer $k \ge 5$, the number of Latin tableaux of shape $\lambda(k+1)$ satisfies $$\text{latin\_tableaux\_count}(\text{latin\_double\_three\_tail\_shape}(k+1)) = \sum_{T \in \text{latin\_tableaux}(\text{latin\_double\_three\_tail\_shape } k)} \text{Matrix.permanent}(\text{latin\_top\_row\_availability}(\text{latin\_double\_three\_tail\_shape } k) \, T \, (k+1)).$$
*Proof of Lemma 2.* This is the case of inserting a new first row in the paper's own permanent recursion (its Lemma 5.4). Any tableau $T'$ of shape $\lambda(k+1) = (k+1, k, \dots, 4, 3, 3)$ decomposes uniquely into its top row (row 0 of length $k+1$) and the remaining $k-1$ rows. Shifting the lower rows upward by one index produces a tableau $T$ of shape $\lambda(k) = (k, k-1, \dots, 4, 3, 3)$. The entries of row 0 must form a permutation of $\{1, 2, \dots, k+1\}$ such that for every column $j \in \{0, \dots, k\}$, the value placed in $(0, j)$ does not appear in column $j$ of $T$. In terms of the availability matrix $M = \text{latin\_top\_row\_availability}(\text{latin\_double\_three\_tail\_shape } k) \, T \, (k+1)$, entry $M_{i, j}$ equals 1 if and only if symbol $i+1$ is available in column $j$. A valid top row is therefore a bijection $\sigma : \{0, \dots, k\} \to \{0, \dots, k\}$ such that $M_{\sigma(j), j} = 1$ for all $j$. The number of such bijections is the permanent of $M$. Summing over all valid completions of all tableaux $T$ of shape $\lambda(k)$ yields the identity.
Lemma 3 (latin_double_three_tail_four_extensions). For any integer $k \ge 5$ and every Latin tableau $T \in \text{latin\_tableaux}(\text{latin\_double\_three\_tail\_shape } k)$, the permanent of the top-row availability matrix of width $k+1$ is 4: $$\text{Matrix.permanent}(\text{latin\_top\_row\_availability}(\text{latin\_double\_three\_tail\_shape } k) \, T \, (k+1)) = 4.$$
*Proof of Lemma 3.* The Lean proof goes through the symbol sets of the columns. In $\lambda(k)$ (columns indexed from 0), columns $0, 1, 2$ have $k-1$ cells each and column $j$ has $k-j$ cells for $3 \le j \le k-1$; in particular column $k-2$ has two cells and column $k-1$ has one. Say a tableau $T$ of shape $\lambda(k)$ has the *canonical profile* if there are $s \in \{1,2,3\}$ and $c \in \{0,1,2\}$ such that
- column $c$ contains the symbols $\{1, \dots, k-2\} \cup \{k\}$, and the other two of the columns $0, 1, 2$ contain $\{1, \dots, k-1\}$;
- column $j$ contains $\{1, \dots, k-j\}$ for $3 \le j \le k-3$;
- column $k-2$ contains $\{1,2,3\} \setminus \{s\}$, and column $k-1$ contains $\{s\}$.
*Step (a): every tableau of shape $\lambda(k)$, $k \ge 5$, has the canonical profile.* This is an induction on $k$. For $k = 5$ it is checked over all tableaux of shape $(5,4,3,3)$. For the step, a tableau of shape $\lambda(k+1)$ is a tableau $T$ of shape $\lambda(k)$ with a top row of length $k+1$ placed above it; by induction $T$ has the canonical profile, and the analysis of step (b) below shows which symbols the top row can place in each column. Adding them to the column sets of $T$ gives the canonical profile of shape $\lambda(k+1)$: the two columns among $0, 1, 2$ holding $\{1,\dots,k-1\}$ receive $k$ and $k+1$, one becoming $\{1,\dots,k\}$ and the other $\{1,\dots,k-1\} \cup \{k+1\}$; column $c$ receives $k-1$ and becomes $\{1,\dots,k\}$; column $j$ with $3 \le j \le k-3$ receives $k-j+1$; column $k-2$ receives $s$ and becomes $\{1,2,3\}$; and columns $k-1$ and $k$ receive the two symbols of $\{1,2,3\} \setminus \{s\}$, so that column $k-1$ holds two of $\{1,2,3\}$ and column $k$ holds the third.
*Step (b): a tableau with the canonical profile has exactly four valid top rows of length $k+1$.* A top row is a bijection from the columns $0, \dots, k$ to the symbols $1, \dots, k+1$ with no symbol placed in a column that already contains it. The two columns among $0, 1, 2$ holding $\{1,\dots,k-1\}$ can only take $k$ and $k+1$, so they take exactly these two symbols, in one of two orders. Column $c$ can then only take $k-1$. Going right, column $j$ for $j = 3, \dots, k-3$ can only take symbols at least $k-j+1$, and all larger ones are used, so it takes $k-j+1$; this uses up $4, \dots, k-2$. The symbols $1, 2, 3$ remain for columns $k-2$, $k-1$, $k$. Column $k-2$ contains $\{1,2,3\} \setminus \{s\}$, so it takes $s$, and columns $k-1$ and $k$ take the other two in either order (column $k-1$ contains only $s$, and column $k$ is empty). That gives $2 \cdot 2 = 4$ top rows, so the permanent of the availability matrix is 4.
*Proof of the Main Theorem.* We combine Lemmas 1, 2, and 3 to prove latin_double_three_tail_count_formula by induction on $k \ge 5$.
In the base case $k = 5$, Lemma 1 (latin_double_three_tail_count_base) establishes that $$\text{latin\_tableaux\_count}(\text{latin\_double\_three\_tail\_shape } 5) = 144.$$ Since $9 \cdot 4^{5-3} = 9 \cdot 4^2 = 9 \cdot 16 = 144$, the base case holds by direct numerical evaluation.
For the induction step, assume as the induction hypothesis that for some $k \ge 5$, $$\text{latin\_tableaux\_count}(\text{latin\_double\_three\_tail\_shape } k) = 9 \cdot 4^{k-3}.$$ We wish to compute the count for $k+1$. Applying Lemma 2 (latin_double_three_tail_count_step), we write the count of tableaux of shape $\lambda(k+1)$ as $$\sum_{T \in \text{latin\_tableaux}(\text{latin\_double\_three\_tail\_shape } k)} \text{Matrix.permanent}(\text{latin\_top\_row\_availability}(\text{latin\_double\_three\_tail\_shape } k) \, T \, (k+1)).$$ By Lemma 3 (latin_double_three_tail_four_extensions), each term in this sum is identically 4. Replacing each permanent by 4 across the summation gives $$\sum_{T \in \text{latin\_tableaux}(\text{latin\_double\_three\_tail\_shape } k)} 4.$$ Summing the constant 4 over the finite set of Latin tableaux produces the product $$\text{latin\_tableaux\_count}(\text{latin\_double\_three\_tail\_shape } k) \cdot 4.$$ Substituting the induction hypothesis into this expression yields $$(9 \cdot 4^{k-3}) \cdot 4.$$ Because $k \ge 5$, the exponent arithmetic satisfies $(k+1) - 3 = (k - 3) + 1$, and by the law of exponents $4^{(k-3)+1} = 4^{k-3} \cdot 4$. Rewriting the product gives $$9 \cdot 4^{(k+1)-3},$$ which completes the inductive step and proves the theorem for all $k \ge 5$.
5. Discussion
The theorem latin_double_three_tail_count_formula completely settles Conjecture 6.3 of arXiv:2610.29291. The question as posed asked whether the number of Latin tableaux of shape $\lambda = (k, k-1, \dots, 4, 3, 3)$ and type $\lambda'$ is equal to $9 \cdot 4^{k-3}$ for every integer $k \ge 5$. The theorem establishes this equality in full generality, answering the question affirmatively for the entire infinite family.
Since $9 \cdot 4^{k-3} > 0$, every shape $(k, k-1, \dots, 4, 3, 3)$ with $k \ge 5$ is Latin. The paper points out that none of these shapes for $k \ge 6$ was known to be Latin by any result, and that already for $(6,5,4,3,3)$ a new technique would be needed; the column-profile argument above is one, for the whole family.
The proof strategy relies on the pointwise four-extension property formulated in Lemma 3 (latin_double_three_tail_four_extensions), combined with the inductive step in Lemma 2 (latin_double_three_tail_count_step) and the base evaluation in Lemma 1 (latin_double_three_tail_count_base). In general counting problems for Latin tableaux, the number of ways to extend a tableau by a new row can vary substantially depending on the column entries of the individual tableau. Here, however, every tableau of shape $(k, k-1, \dots, 4, 3, 3)$ has an availability matrix whose permanent is identically equal to 4. This uniform behavior reduces the sum of permanents in the step formula directly to scalar multiplication by 4.
Regarding what the result does not cover, the enumeration applies strictly to the family of Young diagrams with a double-three staircase tail:
- The theorem is stated for $k \ge 5$, the range of Conjecture 6.3; smaller $k$ are not treated.
- The result does not cover tableaux of shapes other than $(k, k-1, \dots, 4, 3, 3)$, such as staircases with different tail lengths or Young diagrams with other partition structures.
Finally, the provided source material names no further open questions or conjectures beyond Conjecture 6.3. Because latin_double_three_tail_count_formula proves the exact formula for all $k \ge 5$, the question posed in arXiv:2610.29291 regarding this infinite family is completely closed.
Why it is research-level
- settles OP-512 (Exact enumeration of Latin tableaux with a double-three staircase tail)
Lean declarations
- 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…
- 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_count_baseThere are exactly 144 Latin tableaux of shape (5,4,3,3).
- latin_double_three_tail_count_stepThe number of tableaux of the next shape is the sum of availability permanents over all tableaux of the previous shape.
- latin_double_three_tail_four_extensionsConjecture: every Latin tableau of shape (k,k-1,...,4,3,3), k at least 5, extends in exactly four ways after adding the next top row of…
Each one elaborated against Mathlib, and #print axioms returned
nothing outside Classical.choice · Quot.sound · propext.
References
- arXiv:2610.29291 — Counting and constructing Latin tableaux
Drafted by gemini-3.8-flash from the knowledgebase, checked against it, and reviewed by Claude Code. Only the Lean is verified; the prose is a reading of it.