Abstract
This research provides a rigorous formal proof for Doyle’s formula, a combinatorial method for counting $k \times n$ Latin rectangles. Utilizing optimized parallel computing and symmetry exploitation, the authors extend known integer sequences for $k=4, 5, \text{ and } 6$, uncovering significant patterns in prime divisors that inform new conjectures in the field.
Introduction
A Latin rectangle is a $k \times n$ matrix where each row and column contains distinct symbols from the set $\{1, 2, \dots, n\}$. While counting these objects is straightforward for small $k$, the complexity grows exponentially as $k$ increases. For decades, researchers relied on brute-force enumeration or limited recurrence relations. Although a general formula was proposed by Doyle around 1980, it lacked a formal proof and remained computationally underutilized. This paper bridges the gap between theoretical formulation and practical large-scale computation.
Methodology
The authors' approach is divided into theoretical proof and computational optimization.
- Formal Proof: Using Inclusion-Exclusion on ordered $n$-tuples of columns and Möbius Inversion, the authors provide the first rigorous proof of Doyle’s formula for arbitrary $k$.
- Computational Implementation: To handle the formula's complexity, the authors implemented:
- Parallelization: Partitioning the workload of non-negative integer vectors across multiple CPU cores.
- Symmetry Exploitation: Utilizing a group $G$ of order $(k-1)!$ to reduce iterations by calculating only one representative per orbit.
Data and Validation
The study validates its methodology against established values for $k=3$ found in the Online Encyclopedia of Integer Sequences (OEIS).
The authors extended these datasets significantly:
- $k=4$: Up to $n=150$ (extending OEIS A000573).
- $k=5$: Up to $n=40$.
- $k=6$: Up to $n=15$.
Key Insights
- Polynomial Reduction: For a fixed $k$, Doyle’s formula components reduce to fixed multivariate polynomials, transforming the problem into an iterative vector search.
- Divisor Trends: Analysis of $p$-adic valuations revealed linear growth trends in prime divisors (specifically 2 and 3) relative to $n$.
- Combinatorial Connections: The paper reinforces the link between three-line Latin rectangles and the problème des ménages.
Results and Conjectures
The computational effort produced $R_{5,40}$, a 73-digit number, and a 50-digit result for $k=6, n=15$. These new data points led to:
- Question 4: Proposing a lower bound for prime power divisors $p^a$ of $R_{k,n}$ when $p < k$.
- Conjecture 5: Predicting the specific conditions under which the power of 2 dividing normalized $3 \times n$ Latin rectangles matches the power of 2 dividing $n!$.
Conclusion
While the combinatorial explosion limits $k=7$ and beyond, this work significantly advances our ability to enumerate Latin rectangles. Future research will focus on deriving explicit recurrence polynomials for $k=4$ and proving the newly established conjectures regarding prime power divisors.
Summary updated