On Computing the Number of Latin Rectangles

Rebecca J. Stones, Sheng Lin, Xiaoguang Liu, Gang Wang

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.

  1. 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$.
  2. Computational Implementation: To handle the formula's complexity, the authors implemented:
  3. Parallelization: Partitioning the workload of non-negative integer vectors across multiple CPU cores.
  4. 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).

Table 1: Values for $k=3$ Latin rectangles used for validation, referencing OEIS sequences A000186 and A001623.

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

Abstract

Doyle (circa 1980) found a formula for the number of $$k \times n$$ k × n Latin rectangles $$L_{k,n}$$ L k , n . This formula remained dormant until it was recently used for counting $$k \times n$$ k × n Latin rectangles, where $$k \in \{4,5,6\}$$ k ∈ { 4 , 5 , 6 } . We give a formal proof of Doyle’s formula for arbitrary k. We also improve a previous implementation of this formula, which we use to find $$L_{k,n}$$ L k , n when $$k=4$$ k = 4 and $$n \le 150$$ n ≤ 150 , when $$k=5$$ k = 5 and $$n \le 40$$ n ≤ 40 and when $$k=6$$ k = 6 and $$n \le 15$$ n ≤ 15 . Motivated by computational data for $$3 \le k \le 6$$ 3 ≤ k ≤ 6 , some research problems and conjectures about the divisors of $$L_{k,n}$$ L k , n are presented.
BibTeX
@article{stones2016computing,
  author = {Rebecca J. Stones and Sheng Lin and Xiaoguang Liu and Gang Wang},
  title = {{On Computing the Number of Latin Rectangles}},
  journal = {Graphs Comb.},
  year = {2016},
  doi = {10.1007/s00373-015-1643-1},
}
Figure