Asymptotic enumeration of $k\times n$ Latin rectangles for all $k$ (Erdős #725)
Statement
Give an asymptotic formula for the number $L(k,n)$ of $k\times n$ Latin rectangles — $k\times n$ arrays with entries from $\{1,\ldots,n\}$ in which every row is a permutation of $\{1,\ldots,n\}$ and no column repeats an entry. The asymptotic is sought as $n\to\infty$ with $k$ allowed to grow with $n$; the fully general case (up to $k=n$, the enumeration of Latin squares) is wide open.
Acceptance. FULLY RESOLVES: a proof of an asymptotic formula for $L(k,n)$ valid for all $1\leq k\leq n$ as $n\to\infty$ (equivalently, uniform in $k$ — this includes the Latin-square case $k=n$) — a complete written proof with all steps, or machine-checkable. A computation alone cannot close this. ADVANCES: a proof extending the range of validity of an asymptotic formula strictly beyond the widest range stated in the background ($k=o(n^{6/7})$); an asymptotic formula for $L(n,n)$ strictly sharper than the log-scale estimate stated in the background, with proof; new exact values of $L(k,n)$ beyond the published tables (e.g. new terms consistent with and extending OEIS A001009), delivered with the enumeration code and an independent cross-check (two distinct methods or a verifiable certificate); or a numerically certified test of a conjectured next-order correction term against exact counts, with reproducible code. Deliver the proof file, or the enumeration code plus the new exact-count table and cross-check transcript.
Background
Asked by Erdős [Er81]; listed as open on erdosproblems.com/725 (fetched 2026-07-13, status 'open'). Erdős and Kaplansky [ErKa46] proved $$L(k,n)\sim e^{-\binom{k}{2}}(n!)^k$$ for $k=o((\log n)^{3/2-\epsilon})$, and Yamamoto [Ya51] extended this range to $k\leq n^{1/3-o(1)}$. Beyond the problem page's citations, Godsil and McKay ('Asymptotic enumeration of Latin rectangles', J. Combin. Theory Ser. B, 1990) pushed the asymptotic formula further, to $k=o(n^{6/7})$, with a refined correction factor. For $k$ proportional to $n$ — in particular the count of Latin squares $L(n,n)$ — only a log-scale asymptotic is known ($L(n,n)=((1+o(1))e^{-2}n)^{n^2}$, via the Egorychev–Falikman permanent lower bound and Brégman's upper bound); no genuine asymptotic formula is known there, and exact values of $L(n,n)$ stop at $n=11$. The counting sequence for Latin rectangles is OEIS A001009. Topically adjacent (but a different question) is the venue problem on lower bounds for mutually orthogonal Latin squares (Erdős #724). The attacker's tool: permanent-based exact enumeration (inclusion–exclusion over column patterns) to extend the exact tables of $L(k,n)$ beyond the published range with reproducible code, numerical certification of refined asymptotic expansions against the exact counts, and complex-martingale/switching methods from modern asymptotic enumeration for widening the proved range of $k$.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #725 (T. F. Bloom) | website |
| REF-02 | OEIS A001009 — number of Latin rectangles | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.