On Computing the Number of Latin Rectangles

Abstract

Doyle (circa 1980) found a formula for the number of $$k \times n$$ Latin rectangles $$L_{k,n}$$ . This formula remained dormant until it was recently used for counting $$k \times n$$ Latin rectangles, where $$k \in \{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}$$ when $$k=4$$ and $$n \le 150$$ , when $$k=5$$ and $$n \le 40$$ and when $$k=6$$ and $$n \le 15$$ . Motivated by computational data for $$3 \le k \le 6$$ , some research problems and conjectures about the divisors of $$L_{k,n}$$ are presented.

Locations

• Graphs and Combinatorics - View - PDF